字符串匹配算法之KMP
KMP算法最主要的地方是求next数组，next数组保存的是当前失配节点（下标index）之前的子串subString，求出subString的所有前缀子串后缀子串中长度最长的值value，再将该值保存到next[index] = value。
-
代码实现（java版本）
class KMPDemo{ public static int KMP(String mainString, String subString){ int m = mainString.length(); int n = subString.length(); char[] a = mainString.toCharArray(); char[] b = subString.toCharArray(); int[] next = getNext(subString); int j = 0; for(int i = 0; i < m; i++){ while(j > 0 && a[i] != a[j]){ //如果当前字符不匹配，则j需要回到j之前的子串中， //最长前缀和后缀子串的长度的下一个字符。 j = next[j - 1] + 1; } if(a[i] == b[j]) j++; if(j == n) return i - n + 1; } return -1; } public static int getNext(String str){ int len = str.length(); char[] ch = str.toCharArray(); int k = -1; int[] next = new int[len]; next[0] = -1; for(int i = 1; i < len; i++){ while(k > -1 && ch[k + 1] != ch[i]){ /* * 开始时k的值为字符串的[0:i-1]子串的最长相同前缀和后缀子串的长度, * 当之前的i加一后变成现在的i（即上面的i-1 ---> i）后， * 当ch[k+1] ！= ch[i]时， * 需要将k更新为前k个字符的最长相同前后缀子串的长度值, * 所以 k = next[k] */ k = next[k]; } if(ch[k + 1] == ch[i]) k++; next[i] = k; } } }
