KMP算法理解
KMP算法是什么
引用来自维基百科的一段话
在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。
现在用我的话来解释
KMP算法原理就是说就是减少重复的比对项，也就是对字符串匹配暴力算法的一种优化。
暴力算法
一般的字符串匹配解法是将 2 个串的字符进行挨个比较，相当于是把每个字符都比较了一遍，这样是一定能得到结果的，不过显然这样操作导致的时间复杂度是O(m∗n)，也就是 2 个字符串的长度之积，俗称暴力解法。
用图像表示暴力解法的过程如下：
一开始，i 和 j 分别指向主字符串和子字符串，
一般的字符串匹配解法是将 2 个串的字符进行挨个比较，相当于是把每个字符都比较了一遍，这样是一定能得到结果的，不过显然这样操作导致的时间复杂度是O(m∗n)，也就是 2 个字符串的长度之积，俗称暴力解法。
用图像表示暴力解法的过程如下：
一开始，i 和 j 分别指向主字符串和子字符串，
这个时候开始比较 t[i] 和 p[j]，如果匹配则 i 和 j 同时向右移动一格，这样 i 和 j 同时移动到了位置 3，
此时 i 和 j 不匹配了，需要对 i 和 j 进行回退，i 回退到了它最开始的下一位置，即位置 1，而 j 回退到位置 0
此时 i 和 j 仍然不匹配，i 继续向右移动一格，即位置 2，j 依然保持位置 0
如此反复，每当不匹配时，i 都会回到开始匹配的位置同时移动一格，而 j 回到位置 0，当匹配时，i 和 j 同时向右移动，直到 j 到达子字符串的末尾。
代码展示
public static int Befalgorithm(String text, String pattern) {
for (int i = 0; i 0) {
j = next[j - 1];
} else {
i++;
}
}
if (j == n2) {
return i - j;
}
}
return -1;
}
求解字符串最长公共前后缀
最后，我们还剩下一个问题，如何求 next 数组，也就是求模式字符串各个子串的最长公共前后缀长度。
我们先初始化一个和模式字符串长度相等的 next 数组，在 next 数组中，第 1 位默认为 0，因为我们规定只有一个字符的字符串没有前缀和后缀，自然公共前后缀长度只能是 0。
我们依然设定 2 个指针 i 和 j，j 指向位置 0，i 从位置 1 开始依次为 next 数组进行赋值
我们可以把这个过程依然看作是 2 个字符串的比较，j 指向的是模式字符串的前缀，而 i 指向的是模式字符串的后缀
和上面的字符串匹配一样，我们执行同样的处理：
对 next [1] 赋值：i 和 j 不匹配，同时 j 已经是字符串开头，赋值 0
对 next [2] 赋值，i 和 j 匹配，此时 j 为 0，代表只有 1 个字符匹配 (j+1)，赋值 1
对 next [3] 赋值，i 和 j 匹配，此时 j 为 1，代表有 2 个字符匹配 (j+1)，赋值 2
对 next [4] 赋值，i 和 j 不匹配，此时 j 为 2，可以得知 j 前面的字符是 ab，而 ab 的最长公共前后缀长度就是 next[1]，这个值我们前面已经求得了结果是 0，所以 j 回退到位置 0，用代码表示就是 j=next[j-1]
此时 i 和 j 仍然不匹配，但是 j 已为 0，无法继续回退，所以直接对 next [4] 赋值为 0
实际上，我们在求解模式字符串 ababc 的最长公共前后缀长度的时候，不可避免的会对它的子串进行求解，这样可以方便在不匹配时进行回退，这也是动态规划的思想，要求的结果可以用先前已经求得的结果得出。而我们本身就是要对模式字符串的各个子串进行求解，所以可谓一举两得。
public static int[] getNext(String p) {
int[] next = new int[p.length()];
int n = p.length();
int i = 1;
int j = 0;
while (i 0) {
j = next[j - 1];
} else {
next[i] = 0;
i++;
}
}
}
return next;
}
对比一下上一段的字符串匹配代码，可以发现，2 段代码的执行逻辑几乎一模一样，不同之处只是我们在比较过程中插入了对 next 数组进行赋值的代码。
可以这样理解，在字符串匹配中，i 指向的是主串，j 指向的子串，比较的是主串和子串。而在求公共前后缀的时候，我们相当于把模式字符串拆成了前后两部分，同样是对这 2 部分进行字符串匹配，相当于自己比自己。
以上就是 KMP 算法的核心原理及实现，当然，实现方式并不是只有我这一种，KMP 的实现算法多种多样，包括生成的 next 数组都会不一样，而我这里的代码只是希望能够把 KMP 的思路表述清楚：
