KMP 的小记录

之前每次在做题的时候，都没法很好的理解 KMP 算法的思路，每次都是写的磕磕绊绊的，导致没法很好的利用 KMP 来完成相应的习题。这次想借这个机会总结一下 KMP。希望对自己有帮助，如果能对看文章的您有一丝丝帮助，万分荣幸。

KMP 算法：就是三个外国大佬设计的方法，取了每个人名字的一个字母，组成了这个名字。算法时间复杂度为 O（两个字符串长度和）主要是用在了字符串的模式匹配上面。核心主要是利用匹配失败的信息来完成下一次匹配。在 Leetcode 上面的标准习题就是各种字符串之间的互相匹配，这种习题，一般暴力法是肯定可以解决的，但是还有 KMP 的算法值得一试。

算法大致思路：m=aaaccaaad n=aaad，要在 m 中找到 n 的匹配信息

1、 首先从左开始匹配 m，n 发现到了第一个 c 处开始无法匹配

2、 这时候比较基础的就是，从下一个字符开始继续比较，这种就是暴力解法。

3、 所以就需要根据之前的正确匹配的结果去滑动，就可以避免多次暴力求解过程中的多次重复求解。

上面的逻辑一般在很多地方都可以看到，一般询问最多的是 next 数组是怎么求解出来的。其实就是首位重合的字符的个数。next[j+1]=next[j]+1;比如 abaabcabc 的情况，

位序       1   2   3   4   5   6   7   8   9   

模式串     a   b   a   a   b   c   a   b   c   

next 值     0   1   1   2   2   3   1   2   3   

int GetNext(char ch[],int next[]){    int len = ch.length;    next[1] = 0;    int i = 1,j = 0;    while(i< len){        if(j==0||ch[i]==ch[j]) next[++i] = ++j;        else j = next[j];    }}

1.第一位的 next 值为 0

2.第二位的 next 值为 1

后面求解每一位的 next 值时，根据前一位进行比较

3.第三位的 next 值：第二位的模式串为 b ,对应的 next 值为 1;将第二位的模式串 b 与第一位的模式串 a 进行比较，不相等；则第三位的 next 值为 1(其他情况均为 1)

4.第四位的 next 值：第三位的模式串为 a ,对应的 next 值为 1;将第三位的模式串 a 与第一位的模式串 a 进行比较，相同，则第四位的 next 值得为 1+1=2;以此类推。

对应习题：

459： https://leetcode-cn.com/problems/repeated-substring-pattern/

28： https://leetcode-cn.com/problems/implement-strstr/

686：https://leetcode-cn.com/problems/implement-strstr/