-
同学们，如果我们要判断下图
ababababc中是否有ababc和所在的位置，正常是不是需要按下标一个个比，然后不同的时候i再从上次比较的下一个i1开始，步骤如下：
细心的同学会发现其实还是有优化空间的，分析一下，我们在下面图1这个时候下一步可不可以让
i不回退到i1的下一个位置而是继续往下走呢，其实是可以的，只是我们需要满足条件：下面一组字符串不再拿"ababc"去从i位置比较，而是拿"abc"继续从i位置比较，因为前面的"ab"是相同的，没必要再比较了。那么问题来了，我们应该怎么样知道下面ababc中（也就是下标j）要从哪个地方开始取值再和上面的i开始比较呢。-
上面的分析所以就诞生了KMP算法，让原本的时间复杂度o(m*n)变成了o(m+n)
图1 -
要找出
j下次该出现的位置，我们可以按如下规则 从ababc中找出对应的规律放入数组next中
第一步：先创建数组next，长度和要匹配的字符一样（5），然后把下标0的位置置为0，然后我们再创建2个变量i和j，i从1开始，j从0开始。后面就遵循下面的顺序挨个跑...
1.next[i] = j;
2.i++;
3.相同：j++;不同：j = next[j - 1];
由此我们可以得到数组next为[0,0,1,2,0]，然后我们会发现与ababc对应，next数组里值是0的忽略，看next数组里下标2的值是1，说明当前位置往前面数1个，也就是a在之前ab里有相同的，然后最后一个相同的位置是（值-1）也就是0。我们再看next数组里下标3的值是2，从当前位置往前数2个，也就是ab在之前aba里也有相同的，最后一个值b相同的位置在1位置。是不是很神奇。
-
然后我们把这个next数组套在上面的步骤上，当执行到上面图1的时候，
i不变，j = next[j - 1]，j移到下标2位置，然后再拿i(a)和j(a)比较...以此类推，kmp算法的步骤如下：
好了，思路讲完了我们就发车了
/**
* KMP算法 str字符 dest要比较的字符
*/
public int kmp(String str, String dest) {
//获取next数组
int[] next = getKmpNext(dest);
for (int i = 0, j = 0; i < str.length(); i++) {
//这里用while 如果j替换了位置后发现j的值和i的值还是不对 就会继续往后取值
while (j > 0 && str.charAt(i) != dest.charAt(j)) {
j = next[j - 1];
}
//值是相等的 上面i和这里j都++
if (str.charAt(i) == dest.charAt(j)) {
j++;
}
//找到比较的字符了 返回字符位置
if (j == dest.length()) {
return i - j + 1;
}
}
return 0;
}
/**
* 获取字符的next数组
*/
public int[] getKmpNext(String dest) {
int[] next = new int[dest.length()];
//按文章里：把下标0的位置置为0，然后我们再创建2个变量i和j，i从1开始，j从0开始
next[0] = 0;
//2.i++;
for (int i = 1, j = 0; i < dest.length(); i++) {
//3.相同：j++; 不同：j = next[j - 1];
//不同 这里用while是为了确保j的取值是正确的 可以看如下情况，现在执行到这里的时候
//如果不用while j会取为2，其实这个位置d，在前面是不存在的 应该是0，所以用while
//next[0,0,1,2,0,1,2,3,4,]
// a b a b c a b a b d
// i
// a b a b c a b a b d
// j
while (j > 0 && dest.charAt(j) != dest.charAt(i)) {
j = next[j - 1];
}
//相同
if (dest.charAt(i) == dest.charAt(j)) {
j++;
}
//1.next[i] = j;
next[i] = j;
}
return next;
}
