KMP算法:D.E.Knuth、J.H.Morris和V.R.Pratt三位前辈发表的一个模式匹配算法，可以避免重复遍历的情况
普通的字符串匹配算法： 串S叫做主串，T是要匹配的串叫做模式串，每次从头开始一位位比较，一旦发现不同，将T串向右移动一位，继续从头开始比较。 第一次匹配0，1之后发现2号地址不同，然后开始新一轮的比较，将模式串右移一位，继续从头开始比较 第二次匹配发现1号位置元素不同，继续向后移动一位，知道到四号地址，此时匹配成功。 暴力破解的代码实现：
public static int violentMatch(String s,String t){ char[] chs = s.toCharArray(); char[] cht = t.toCharArray(); int i=0; int j=0; while (i<s.length() && j<t.length()){ if (chs[i] == cht[j]){ //当前字符匹配成功 i++; j++; }else{ i = i-j+1; //从i-j+1开始继续匹配相当于将匹配串T向右移动一位 j = 0; } } if (j == t.length()){ //匹配成功返回成功的起始下标 return i-j; }else{ return -1; } }可以发现，对于模式串T来说，“abd"首字母和后面的串”bd"中任意一个字符都不同。也就是说，对于第一次匹配成功的0，1号地址，a字符不可能和1号地址的元素相等，那么第二次匹配其实是不需要的。 上面这一步是不需要的，直接将T串移动两个位置开始比较，如下图 我们可以发现如果模式串里相同的字符为0时，每次匹配成功n个字符，下一次就可以向右移动n个位置，那么如果有相同的字符怎么办。 如图，主串是abcababa,模式串是abcabx 如果5号地址元素不匹配，但是模式串的前缀ab和x之前的后缀ab相等，下一次只需将T移动三个位置继续匹配，此时从五号位置开始比较。也就是说向右移动多少取决于T串的结构，准确来说就是当前字符的前后缀相似度，总结如下 把T串各个位置向右移动的位置大小也就是j值的变化定义为一个next数组，next[j]的值 1 当j = 1时，不比较 next[j] = max{k, 1 <= k < j 且"t1 … tk-1” = “tj-(k-1) … tj-1”} 0 其他情况
kmp算法流程：
如果j = -1，或者当前字符匹配成功（即chs[i] == cht[j]），都令i++，j++，继续匹配下一个字符；如果j != -1，且当前字符匹配失败（即chs[i] != cht[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串T相对于主串S向右移动了j - next [j] 位。 换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值即移动的实际位数为：j - next[j]，且此值大于等于1。KMP实现代码 求next数组值代码如下：
public static int[] getNext(String t,int[] next){ int length = t.length(); char[] chars = t.toCharArray(); next[0] = -1; int k = -1; //k表示前后缀相等的最大个数 int j = 0; // while (j<length-1){ // chars[k]表示k个相同前后缀增加的下一个元素，chars[j]当前求next值的元素 //两个值相等，即next+1，如果不相等 相等的元素k就是next[k]的值 //k=-1 表示刚开始，即j=0，k = 0时 表示没有相等的前后缀 //规律？ 出第一个next[0]=-1外，每一个元素的next数组值只可能是 0或者前一个next+1. if (k == -1 || chars[j] == chars[k]){ //普通求next ++k; ++j; next[j] = k; //优化后求nextValue /*++k; ++j; if (chars[j] != chars[k]) next[j] = k; else //当chars[j] = chars[next[j]]即chars[k],下一次比较的一定是chars[next[j]] == s[i] //肯定是不相等的，因为chars[j] != s[i] next[j] = next[k];*/ }else{ k = next[k]; //要移动的位数k - next[k]位； } } return next; }KMP的实现代码：
public static int kmp(String s,String t,int[] next){ int i = 0; int j = 0; char[] chs = s.toCharArray(); char[] cht = t.toCharArray(); int sLen = s.length(); int tLen = t.length(); while(i<sLen && j<tLen){ /* j = -1考虑的是第一个字符不相等的情况。 因为next[0] = -1,如果刚开始主串和模式串第一个字符不匹配，那么j=next[0]=-1, */ if (j == -1 || chs[i] == cht[j]){ i++; j++; }else{ j = next[j]; //相当于模式串向右移动的位数为j-next[j]; } } if (j == tLen){ //代表成功匹配，j到达了模式串的末位 return i-j; }else{ return -1; } }学习kmp算法的参考
《大话数据结构》 程杰著https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html