KMP算法是一种经过改良的字符串匹配算法，其实按我的理解，这不仅可以用于字符串，它可以在有顺序的任何集合里查找有序子集是否存在。而对字符串而言，在java中其实功能跟String.indexof方法是一样的。

准备工作

这篇文章中我们先定义一些名称，假设我们从字符串a中查找是否存在字符串b，那么a就叫目标字符串，b就叫模式字符串。我们设a的长度为m，b的长度为n。

暴力查找

首先我们不考虑什么KMP，如果要自己来实现indexof方法，首先想到的就是暴力查找，也就是从目标字符串的开头一个个比对每个字符是否跟模式字符串相同，如果发现有不同的就从目标字符串的下一个字符开始再查找，直到找到匹配的情况或者找完整个目标字符串。代码如下：

    public static int sfClumsyPatternSearch(String target, String pattern){
        char[] cTarget = target.toCharArray();
        char[] cPattern = pattern.toCharArray();
        int targetPointer = 0;
        int patternPointer = 0;
        while(targetPointer < cTarget.length){
            int charInTarget = cTarget[targetPointer];
            int charInPattern = cPattern[patternPointer];
            if(charInPattern == charInTarget){
                if(patternPointer == cPattern.length - 1){
                    return targetPointer - cPattern.length + 1;
                }
                targetPointer++;
                patternPointer++;
            }else{
                targetPointer = targetPointer - patternPointer + 1;
                patternPointer = 0;
            }
        }
        return -1;
    }

这种方法确实可用，但性能上就不容乐观了，考虑最坏的情况的话，也就是找不到匹配的情况时，它的时间复杂度是O((m-n)n)，既然是最坏情况，目标串的长度应该是远大于模式串的，那此时复杂度就等于O(mn)。
通过上面的代码我们可以看到，当发现了不匹配的字符时，目标串指针会往回移动到左起下一个位置。如下图：

图1-目标串指针的冗余移动

暴力查找的弊端

第一轮比较，目标串指针从索引0开始比较，当比较到模式串最后一位时，发现字母不同，按上面的算法，下一轮比较时，目标串的指针会移动到蓝色方框所在的位置，模式串指针会移动到索引0位置继续比较。显然，这增加了无用的比较次数，如果我们用肉眼观察，很容易会发现目标串当前位置之前的ABAEAB跟模式串的开头完全匹配，所以完全可以让目标串指针不动，模式串指针移动到ABAEAB之后的位置继续比较，这样就减少了很多计算次数。那么如何应用这一特性呢？仔细观察我们可以发现，凡是符合这样情况的模式串都有这样的一种特征，即模式串开头方向和不同字母索引之前算起的方向存在完全相同的字符序列（可以相交），如下图：

图2-模式串中的相同部分

我们看到，左侧红框圈出的序列跟右侧蓝框圈出的序列完全相同，比较进行到最后的字母A发现不匹配时，之前比较过确定匹配的部分实际上是蓝框圈出的部分，但由于蓝框圈出的部分跟红框的部分完全相同，那也就相当于比较完了红框圈出的部分，所以，可以让目标串指针不动，模式串指针直接移动到红框部分的下一位。

以上思路如果想让程序实现，必须让他更具体，具体到什么呢？当然是具体到跳转的索引位置，那接下来我们要做的就是建立一个数组，它的长度跟模式串相等，它存放的则是当不匹配的情况出现时，模式串指针将要跳转的下一个索引位置，也就是说，next数组存放的其实是索引值。

确定next数组

怎么计算这个数组的值？首先得想想我们的目的是干什么，那就是看在出现不匹配的字符位置之前的模式串部分中首尾是否有相同的部分，这个相同部分可以是一位，也可以是连续的n位，所以我们计算的原则就是在 模式串 中：
1.从头开始比较两位的值，如果相等则希望相等的位数更长，具体做法就是两个指针全右移一位再比较，此时右侧指针指向的位置赋值为左侧指针的索引加1，因为截止到右指针的位置，模式串中首尾存在相同部分，那么当下一位不匹配时，应该把模式串指针移动回数组左侧相同部分的下一位继续比较。
2.如果不相等就比较下一个字符是否相等，这里就有两种情况了，具体对应两个指针，那就是左指针a往左移动或右指针b往右移动，因为右端点是循环终止条件，所以我们的做法肯定是先a左再b右，碰到左右指针指向的字母相同时则让next数组中右指针指向的位置值等于左指针索引加1，原因同第一条。
3.重复这个过程直到数组装满值。

用next数组辅助查找

现在模式串已经确定，那么就可以用它配合来查找了。具体做法前面跟暴力法一样，目标串指针跟模式串指针都往后移动比较元素，如果遇到不同的情况，就把模式串指针移动到next数组前一位存放的索引值处，目标串指针不动，重复这个过程直到模式串指针移动到最后位置，这就说明已经找到了匹配的串。如果目标串指针移动到了目标串最后一位，模式串指针还没移动到模式串最后一位，那就证明没找到，返回-1。
具体代码如下所示：

    public static int kmpSearch(String target, String pattern){
        char[] cTarget = target.toCharArray();
        char[] cPattern = pattern.toCharArray();
        //生成next数组
        int[] nexts = new int[cPattern.length];
        //因为下面的循环是以j索引来赋值，j又大于i，所以应该初始化一下i的值
        //int数组不初始化默认值也是0，这里只为了表达逻辑
        nexts[0] = 0;
        for(int i = 0, j = 1; j < cPattern.length; ){
            if(cPattern[i] == cPattern[j]){
                nexts[j++] = ++i;
            }else{
                //下面的while和if实际上是互斥关系，如果你尝试用if else来写会发现存在冗余逻辑，所以改成这样
                while (i > 0){
                    i = nexts[i-1];
                    if(cPattern[i] == cPattern[j] || i == 0){
                        nexts[j] = i;
                        break;
                    }
                }
                if(i == 0)
                    j++;
            }
        }
        //用next数组来在目标串中查找模式串
        int targetPointer = 0;
        int patternPointer = 0;
        while(targetPointer < cTarget.length){
            if(cTarget[targetPointer] == cPattern[patternPointer]){
                patternPointer++;
            }else{
                if(patternPointer > 0)
                    patternPointer = nexts[patternPointer - 1];
            }
            targetPointer++;
            if(patternPointer == cPattern.length - 1)
                return targetPointer - cPattern.length + 1;
        }
        return -1;
    }

经验证，以上算法执行结果均符合预期。