简介及引出KMP算法
KMP算法是由Donald Kunth、Vaughan Pratt、James H.Morris三个人发明的，是一种复杂度很小的匹配字符串的算法。
给定两个字符串str和match，长度分别为N和M。实现一个算法，如果字符串str中含有子串match，则返回match在str中的开始位置，不含有则返回-1。
正常的思路，从str[0]开始匹配，如果和match[0]相等，则匹配它们之后的字符是否相等，如果全部相等则含有。但是如果匹配到一定程度发现后边的字符不相等，则再从str[1]开始匹配。不排除str的每个字符都要做匹配的可能性，比如str=”aaaaaaaaab”, match=”aaab”，这样的复杂度为O(N*M)非常高。每一次的检查都是从零开始，所以显得很麻烦。
nextArr
这时候有个解决办法，就是使用KMP算法：
要生成match字符串的nextArr数组，数组长度和字符串长度相等，每一个nextArr[i]都对应一个数字。那么这个nextArr[i]的含义是什么？
在字符串match[0]至match[i-1]中，有包含match[0]且不包含match[i-1]的前缀子串，还有包含match[i-1]且不包含match[0]的后缀子串，两者的最大匹配长度就是nextArr[i]的值。
举例说明：aaaab这个字符串，nextArr[4]，字符b之前的就是aaaa。前缀子串为前三个aaa，后缀子串为后三个aaa，两者的最大匹配长度为3。
另有字符串abc1abc1，nextArr[7]的值也是3，因为abc1abc的前缀子串abc和后缀子串abc相匹配。
知道了nextArr的含义，那么这个数组要如何得到？
因为match[0]前边没有其他字符，所以规定nextArr[0]=-1。另外对于match[1]来说前边只有一个match[0]，所以规定nextArr[1]=0。所以重点放在对match[i] (i>1)时，nextArr的求解。
我们是依次求出nextArr[i]，因此我们在求nextArr[i]的时候，0、1、……i-1的情况都已经考虑过了。nextArr[i]的结果也确实需要前边的结果的帮助来求得。
如图，这是match数组的其中一部分，我们想要知道nextArr[i]的值，nextArr[i-1]已经事先得到了。X和Y分别为在求nextArr[i-1]时的前缀子串和后缀子串。这时候就要分情况考虑：
如果字符B和C相等，那么前缀子串就为X加上字符C，后缀子串就是Y加上字符B，因此nextArr[i]=nextArr[i-1]+1。
如果字符B和C不相等，那又要再分情况考虑：
假设字符C是第cn个字符，即match[cn]，那么nextArr[cn]就是其最长前缀和后缀匹配长度，前缀和后缀分别对应m和n，由于X和Y是相匹配的，所以在Y中有相应的n’与X中的n相匹配。然后就是看字符B和D是否相等。
如果相等，那么可以类似于之前的处理，前缀子串是m加上字符D，后缀子串是n’加上字符B，因此nextArr[i]=nextArr[cn]+1。
如果B和D不相等，那么就要调到字符D，对m进行分割，和前一张图是类似的处理。一致这样处理，都会有字符和B进行比较，只要有相等的情况，那么nextArr[i]就能确定。如果始终没有与B相等的，会最终来到match[0]这个位置，所以就不存在前缀和后缀匹配的情况，那么nextArr[i]=0。
public int[] getNextArray(char[] ms) {
if (ms.length == ) {
return new int[] {-};
}
int[] next = new int[ms.length];
next[] = -;
next[] = ;
int pos = ;
int cn = ;
while (pos < next.length) {
if (ms[pos - ] == ms[cn]) {
next[pos] = cn + ;
pos = pos + ;
} else if (cn > ) {
cn = next[cn];
} else {
next[pos] = ;
pos = pos + ;
}
}
return next;
}
加速匹配
有了nextArr数组，那么如何让匹配过程得到加速？
假设从str[i]开始匹配，匹配到j位置的字符发现与match中的字符不一致，也就是说str[i]到str[j-1]，与match[0]到match[j-i-1]一一对应。直到str[j]与match[j-i]不匹配了。
如上图，我们已经有了nextArr数组，nextArr[j-i]的值表示match[0]到match[j-i-1]这一段字符串前缀与后缀的最长匹配。这个前缀和后缀分别为图中的a和b。
我们下一次的匹配不需要按照传统的方法，从str[i+1]开始，而是依然从str[j]继续向后，让match[k]滑动到了str[j]的位置上。也就是说str中可以一直向后滑动进行匹配，直到在某一位置把match完全匹配完。过程就如下图。
为什么可以这样做？
一开始是匹配的，str中的A字符和match中的B字符不匹配，所以c和b区域是一样的。a和b分别为前缀和后缀，所以a和b也是一样的，所以a和c是一样的。所以将字符C滑动到和A一样的位置继续接下来的匹配，这就相当于从str的c区域的第一个字符重新开始了匹配（c的第一个字符和match[0]相同）。
不过从str[i]到c区域的第一个字符跨度有点大，但是不用担心。
如果要从str[i]和c的第一个字符之间的某个位置进行下一轮的匹配的话，说明要有一对前缀和后缀的长度d和e是大于a和b的，但是a和b本身就是最长的匹配了，前后矛盾，所以之前的处理是没问题的。
str的位置是不会退回的，滑动的最大长度就是str的长度N，所以时间复杂度为O(N)。匹配的代码如下：
public int getIndexOf(String s, String m) {
if (s == null || m == null || m.length() < || s.length() < m.length()) {
return -;
}
char[] ss = s.toCharArray();
char[] ms = m.toCharArray();
int si = ;
int mi = ;
int[] next = getNextArray(ms);
while (si < ss.length && mi < ms.length) {
if (ss[si] == ms[mi]) {
si++;
mi++;
} else if (next[mi] == -) {
si++;
} else {
mi = next[mi];
}
}
return mi == ms.length ? si - mi : -;
}