KMP算法求解的问题

给定两个字符串str和match,长度分别为N和M。实现一个算法,如果字符串str中含有子串match,则返回match在str中的开始位置。不含有则返回-1.

例如:

str=”acbc”,match=”bc”,返回2;

str=”acbc”,match=”bcc”,返回-1;

要求:如果match的长度大于str的长度(M>N),str必然不会含有match,可直接返回-1.但如果N≥M,要求算法复杂度为O(N).

对数器

什么叫对数器呢?

我们可以通过一个事例来了解它,我们在学算法时,一般来说,会学到常见的排序算法(后面也会涉及到),我们在写完排序代码后需要对代码进行验证其正确性,比较常用的做法就是我们自己定义一个数组,然后运行我们的代码,然后我们逐一看结果是否按序排好,这种方式缺点就是不能将所有可能的情况全都覆盖,可能看起来我们的输出的结果没问题,其实在特殊情况下,可能会存在问题。对数器就是生成一个随机数组(数组大小,数组元素范围完全随机),然后将随机数组进行复制,一个数组用我们来进行排序,另一个数组我们一个绝对正确的排序算法来进行排序,将两组数据进行比较,一般来说我们会生成多个数组来进行排序,最终所有的数组排序正确才返回正确,由于数组是随机且大小、元素值都不唯一,而且数组是多组,因此如果再这种情况下返回正确的结果,那么我们就认为我们的算法是正确的。