KMP算法介绍
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度为 O(m+n)
KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次
回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间
举例
- 有一个字符串 S1 = "BBCABCDABABCDABCDABDE" , 搜索词 字符串 S2 = "ABCDABD"
- 现在要判断 S1 是否含有 S2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
- 要求:使用KMP算法完成判断，不能使用简单的暴力匹配算法
解题思路
-
首先，用 S1 的第一个字符和 S2 的第一个字符去比较，不符合，关键词向后移动一位
image.png -
重复第一步，还是不符合，再后移
image.png -
一直重复，直到S1有一个字符与S2的第一个字符符合为止
image.png -
接着比较字符串和搜索词的下一个字符，还是符合。
image.png
5.遇到 S1 有一个字符与 S2 对应的字符不符合。
6.如果按照暴力匹配算法的思路的话， 就会出现如下图的情况， 重复1-5步， 但是这种算法效率太低。
当第5步中空格与 D 不匹配时，你其实知道前面六个字符是”ABCDAB”了， 于是KMP 算法的思想是，设法利用这个已知信息，不要把”搜索位置”移回已经比较过的位置，继续把它向后移，这样就提高了效率。
7.怎么做到把刚刚重复的步骤省略掉?可以对 S2 计算出一张《前后缀最大公共元素表》
8.已知空格与 D 不匹配时，前面六个字符”ABCDAB”是匹配的。查表可知，最后一个匹配字符 B 对应, 对应的子串为ABCDAB，最大的公共元素长度为 2，因此按照下面的公式算出向后移动的位数:
移动位数 = 已匹配的字符数 - 最大的公共元素长度
因为 6 - 2 等于 4，所以将搜索词向后移动 4 位
9.因为空格与C不匹配，搜索词还要继续往后移。这时，已匹配的字符数为 2(”AB”)，对应的”部分匹配值” 为 0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移 2 位。
10.因为空格与 A 不匹配，继续后移一位。
11.逐位比较，直到发现 C 与 D 不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动 4 位。
12.逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索(即找出全部匹配)， 移动位数 = 7 - 0，再将搜索词向后移动 7 位，这里就不再重复了。
搜索词 前后缀最大公共元素表
Java代码实现
import java.util.Arrays;
public class KMP {
public static void main(String[] args) {
String s1 = "BBC ABCDAB ABCDABCDABDE";
String s2 = "ABCDABD";
int[] next = kmpNext(s2);
System.out.println("next=" + Arrays.toString(next));
int index = kmpSearch(s1, s2, next);
System.out.println("index=" + index);
}
/**
*
* @param s1 源字符串
* @param s2 搜索子串
* @param next 搜索子串对应的公共元素表
* @return 如果是-1 就是没有匹配到，否则返回第一个匹配的位置
*/
public static int kmpSearch(String s1, String s2, int[] next) {
//遍历
for(int i = 0, j = 0; i < s1.length(); i++) {
//需要处理 s1.charAt(i) ！= s2.charAt(j), 去调整j的大小
while( j > 0 && s1.charAt(i) != s2.charAt(j)) {
// 找到比对过Match的搜索字符串中的 对应的公共元素个数， 然后再从后一个字符开始比较
j = next[j-1];
}
if(s1.charAt(i) == s2.charAt(j)) {
j++;
}
// 所有的字符串都比对成功， 返回找到的字符串位置
if(j == s2.length()) {
return i - j + 1;
}
}
return -1;
}
/**
* 前后缀最大公共元素表
* @param dest
* @return
*/
public static int[] kmpNext(String dest) {
//创建一个next 数组保存公共元素值
int[] next = new int[dest.length()];
//如果字符串是长度为1 公共元素值就是0
next[0] = 0;
// i=1 搜索字符串从第二个字符开始计算公共元素
for(int i = 1, j = 0; i < dest.length(); i++) {
//当dest.charAt(i) != dest.charAt(j) ，我们需要从next[j-1]获取新的j
while(j > 0 && dest.charAt(i) != dest.charAt(j)) {
j = next[j-1];
}
//当dest.charAt(i) == dest.charAt(j) 满足时，公共元素就 +1
if(dest.charAt(i) == dest.charAt(j)) {
j++;
}
// 第i个元素时， 公共元素的个数
next[i] = j;
}
return next;
}
}
参考
https://www.cnblogs.com/zzuuoo666/p/9028287.html
https://www.bilibili.com/video/BV1E4411H73v?p=162
