KMP算法用于解决传统字符串匹配方法多次重复比较以及特殊情况下多余匹配效率低下的问题，核心思想就是匹配失败时主串指针不回退，模式串指针回退，而且是回退到合适的位置，这个合适的位置是由一个next数组所给出的，而这个next数组的求解却和主串没有关系，给定一个模式串就能得到一个next数组，然后借助这个next数组我们就能拿这个模式串去和任意主串完成匹配，并在线性时间内得到匹配结果。
那么它为什么能保证匹配失败时主串指针不回退只回退模式串指针的情况下不会错过某些匹配结果，为什么一部分中间匹配结果可以不进行，这个next数组又要如何求解，我这里不做解释了，因为比较复杂，我自认为可能说不清楚，我这里只给出实现代码。感兴趣的朋友可以去看这篇文章（原文链接），不得不说，这是我目前看到讲的最详细的一篇了，十分清楚，相信大家都可以看懂。
/**
* KMP算法
* @param haystack
* @param needle
* @return
*/
public int KMP(String haystack, String needle) {
int s = haystack.length();
int t = needle.length();
if (t == 0) return 0;
if (s < t) return -1;
// KMP
int[] next = getNext(needle);
int i = 0, j = 0;
while (i < s && j < t) {
// 模式串挪到了空位置或当前位置匹配，两指针都后移
if (-1 == j || haystack.charAt(i) == needle.charAt(j)){
++i;
++j;
} else {
// 主串指针不动，模式串后移到合适位置
j = next[j];
}
}
// j 挪到最后一个位置，表示模式串匹配成功，i 表示主串挪动的距离，减去模式串的长度就是模式串在主串第一次出现的位置
if (j == needle.length())
return i - t;
return -1;
}
/**
* 根据模式串求next数组，求next数组与主串无关
* next数组记录的是当模式串与主串匹配到p[j]时发生不匹配，此时模式串应回退到那个位置，
* 也就是从j之前哪个位置字符开始跟主串的当前位置继续开始匹配过程
* 至于为什么求最大公共前后缀 参考这篇文章
* https://www.cnblogs.com/zhangtianq/p/5839909.html
* @param pattern
* @return
*/
private int[] getNext(String pattern) {
int[] next = new int[pattern.length()];
next[0] = -1;
// next[0] = -1,表示p[0]就不匹配时，那么p[0]去和主串的下一个位置匹配，表示模式串移到-1的位置
// next[i] = 0，表示p[i]不匹配时，模式串移到0的位置
int j = 0, k = -1;
while (j < pattern.length() - 1) {
// p[0]...p[k-1]p[k]...p[j-k-1]...p[j]
// next[j]代表的是字符j之前子串的最大公共前后缀，也就是 p[0]...p[k-1] = p[j-k-1]...p[j-1]
// 当p[k] = p[j] 时，next[j+1]也就是字符j+1之前的子串的最大公共前后缀，比next[j]多了1，
// 因为总是next[j] = k, 所以 k++即可
if (-1 == k || pattern.charAt(j) == pattern.charAt(k)) {
++j; // 得到next[j+1] = next[j] + 1
++k;
// 当前位置不匹配了，如果下一个位置的字符和当前位置一样，肯定不成功，直接跳到下下个位置
if (pattern.charAt(j) != pattern.charAt(k)) //
next[j] = k; // k 就是最大公共前后缀的长度，next[k]是p[0]...p[k-1]最大公共前后缀
else
next[j] = next[k];
} else
k = next[k];
}
return next;
}
打赏
