内容：
1、问题引入
2、暴力求解方法
3、优化方法
4、KMP算法
1、问题引入
原始问题：
对于一个字符串 str （长度为N）和另一个字符串 match （长度为M），如果 match 是 str 的子串，
请返回其在 str 第一次出现时的首字母下标，若 match 不是 str 的子串则返回 -1
注：子序列和子串的区别：子序列可以不连续，子串必须连续
2、暴力求解方法
暴力求解方法：将 str 从头开始遍历并与 match 逐次比较，若碰到了不匹配字母则终止此次遍历转而从 str 的 第二个字符开始遍历
并与 match 逐次比较，直到某一次的遍历每个字符都与 match 匹配否则返回 -1 。易知此种 做法的时间复杂度为 O(N*M)
注：KMP算法则给出求解该问题时间复杂度控制在 O(N) 的解法
3、优化方法
优化方法：借助next数组进行优化
在一个字符串中，每个字符之前的最长前缀和最长后缀的最大匹配长度就是next数组中的值，next数组在KMP算法中的目的就是决定下次匹配对象
注：前缀不能包含最后一个字符，后缀也不能包含第一个字符(前缀和后缀不能是字符串整体!)
next数组示例：
- 字符串为abcabcd，此时d位置上的next数组值就是3
- 字符串为aaaaab，此时b位置上的next数组值就是4
- 字符串为ababac，此时next数组值依次是-1、0、0、1、2、3
如何求next数组：
当串 match 长度 mlen=1 时，规定 next[0]=-1 。当 mlen=2 时，去掉 match[1] 之后只剩下 match[0] ，
大匹配子串长度为0（因为前缀子串不能包含串尾字符，后缀子串不能包含串首字符），即 next[1]=0
而当 mlen>2 时， next[n] （n>=2）都可以推算出来：
如上图所示，如果我们知道了next[n-1] ，那么 next[n] 的求解有两种情况：如果 match[cn]=match[n-1] ，
那么由a区域与b区域（a、b为最大匹配前缀子串和后缀字串）相同可知 next[n]=next[n1]+1 ；
如果 match[cn]!=match[n-1] ，那么求a区域中下一个能和b区域后缀子串中匹配的较大的一个，
即a区域 的大匹配前缀字串 c区域 ，将 match[n-1] 和c区域的后一个位置（ cn' ）上的字符比较，
如果相等则 next[n] 等于c区域的长度+1，而c区域的长度就是 next[cn] （ next数组的定义如此）；
如果不等则将 cn 打 到 cn' 的位置继续和 match[n-1] 比较，直到 cn 被打到 0 为止（即next[cn]=-1 为止），那么此时next[n]=0
求next数组代码：
public static int[] getNextArray(char[] str) {
if (str.length == 1) {
return new int[] { -1 };
}
int[] next = new int[str.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i < next.length) {
if (str[i - 1] == str[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
}
4、KMP算法
KMP算法的原理如下：
子串 match 的 next数组找到之后就可以进行 KMP 算法求解此问题了。 KMP 算法的逻辑是对于 str 的 i~(i+k) 部分 （ i 、 i+k 合法）
和 match 的 0~k 部分（ k合法），如果有 str[i]=match[0] 、 str[i+1]=match[1] …… str[i+k-1]=match[k-1] ，但 str[i+k]!=[k] ，
那么 str 的 下标不用从i+k 变为 i+1 重新比较，只需将子串 str[0]~str[i+k-1] 的大匹配前缀子串的后一个字符 cn 重新与 str[i+k] 向后依次比较，
后面如果又遇到了不匹配的字符重复此操作即可：
当遇到不匹配字符时，常规的做法是将 str 的遍历下标 sIndex 移到 i+1 的位置并将 match 的遍历下标 mIndex 移到 0 再依次比较，
这种做法并没有利用上一轮的比较信息（对下一轮的比较没有任何优化）；
而 KMP 算法则不是这样，当遇到不匹配的字符str[i+k] 和 match[k] 时， str 的遍历指针 sIndex=i+k 不用动，
将 match 右滑并将其遍历指针 mIndex 打到子串 match[0]~match[k-1]的最大匹配前缀子串的后一个下标 n 的位 置。
然后 sIndex 从 i+k 开始， mIndex 从 n 开始，依次向后比较，若再遇到不匹配的数则重复此过程
KMP算法核心代码：
public static int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
int i1 = 0;
int i2 = 0;
int[] next = getNextArray(str2);
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] == -1) {
i1++;
} else {
i2 = next[i2];
}
}
return i2 == str2.length ? i1 - i2 : -1;
}
可以发现 KMP 算法中 str 的遍历指针并没有回溯这个动作（只向后移动），当完成匹配时 sIndex 的移动次数小 于 N ，
否则 sIndex 移动到串尾也会终止循环，所以 while 对应的匹配过程的时间复杂度为 O(N) ( if(next[j] != -1){ j = next[j] } 的
执行次数只会是常数次，因此可以忽略)
完整的KMP代码及测试样例如下：
// KMP算法
public class KMP {
public static int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
return -1;
}
char[] str1 = s.toCharArray();
char[] str2 = m.toCharArray();
int i1 = 0;
int i2 = 0;
int[] next = getNextArray(str2);
while (i1 < str1.length && i2 < str2.length) {
if (str1[i1] == str2[i2]) {
i1++;
i2++;
} else if (next[i2] == -1) {
i1++;
} else {
i2 = next[i2];
}
}
return i2 == str2.length ? i1 - i2 : -1;
} public static int[] getNextArray(char[] str) {
if (str.length == 1) {
return new int[] { -1 };
}
int[] next = new int[str.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i < next.length) {
if (str[i - 1] == str[cn]) {
next[i++] = ++cn;
} else if (cn > 0) {
cn = next[cn];
} else {
next[i++] = 0;
}
}
return next;
} public static void main(String[] args) {
System.out.println(getIndexOf("abcabcababaccc", "ababa"));
System.out.println(getIndexOf("just a test", "test"));
System.out.println(getIndexOf("justatest", "test"));
System.out.println(getIndexOf("asfawfasdf", "666"));
System.out.println(getIndexOf("absafasdcc", "ababa"));
}
}