1. KMP
在计算机科学中，克努斯-莫里斯-普拉特字符串查找算法（英语：Knuth–Morris–Pratt algorithm，简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前配对的字符。
这个算法由高德纳和沃恩·普拉特在1974年构思，同年詹姆斯·H·莫里斯也独立地设计出该算法，最终三人于1977年联合发表。
通俗点讲：2个字符串，s1和s2, 判断s1是否包含s2, 如果包含返回匹配的起始位置。
2. 算法核心
- 找s2的每一个字符位置index, 的前缀和后缀相等的最长长度（不包含当前index），保存在next数组中。
- 一起从i开始匹配，过程中如果发现s1[cur]不等于s2[cur]，那么s1的指针不需要退回到i+1的位置，s2不需要退回到0的位置，而是s1不变，s2退回到next[cur]的位置（从0开始，next[cur]的值 = 最长前缀长度+1）
2.1 求next数组
next数组的含义为：next[i]中保存的是i位置之前的前缀和后缀相等的最长长度。
- 默认next[0] = -1， 即第一个字符不不满足条件设置为-1
- 默认next[1] = 0，即第二个字符之前的字符就1个，所以的长度最长也就是1
- 在任意i位置的，分2种情况
- 如果arr[i-1] == arr[next[i-1]]，那么next[i] = next[i-1]+1
- 如果arr[i-1] ！= arr[next[i-1]]，那么只能往前找了，设置 cn = next[cn], 然后去看 arr[cn-1] 是否和 arr[next[cn-1]]相等了，然后循环1，2步，如果cn为0时代表next[i] = 0
实现：
public int[] getNextArr(char[] arr){
if(arr.length == 1){
return new int[]{-1};
}
int[] nextArr = new int[arr.length];
nextArr[0] = -1;
nextArr[1] = 0;
//next数组的位置
int i = 2;
int cn = 0;
while (i< nextArr.length){
if(arr[i-1] == arr[cn]){
//此时因为cn = arr[i-1],其实就是：nextArr[i] = arr[i-1] + 1; i++; cn++;
nextArr[i++] = ++cn;
}else if(cn>0){
//cn往前跳，继续去找next[i]的最长前缀
cn = nextArr[cn];
}else {
//cn=0了，代表next[i]没有最长前缀，i++,继续把
nextArr[i++] = 0;
}
}
return nextArr;
}
2.2 为啥s1的可以不会跳回到i+1的位置
- 反证法证明从i+1到j位置，不会匹配出s2
- 利用next数组，s1的位置可以不动，s2的位置从next[cur]开始
3.算法实现
public int getIndexOf(String n, String m){
//要求n>m
if(n == null || m == null || m.length()<1 || n.length() < m.length()){
return -1;
}
char[] str1 = n.toCharArray();
char[] str2 = m.toCharArray();
int i1 = 0;
int i2 = 0;
int[] next = getNextArr(str2);
while (i1 < str1.length && i2 < str2.length){
//如果相等，同时往前推
if(str1[i1] == str2[i2]){
i1++;
i2++;
}else if(i2 == 0 ){//或者 next[i2] == -1
//如果前推到头了，代表以当前位置i开头匹配不出来了，此时需要i1往前走
i1++;
}else {
//如果不相等，i2往前推到最长前缀后一个位置，也就是next[i2]
i2 = next[i2];
}
}
//跳出while，代表有一个越界了，此时如果i2如果在str2.length，代表时可以匹配出来的，否则返回-1
return i2 == str2.length ? i1 - i2 : -1;
}
