KMP算法

算法的背景

KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法

核心思想

KMP 方法算法就利用之前判断过信息，通过一个 next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过 next 数组找到，前面匹配过的位置，省去了大量的计算时间。

算法图解：

当算法移动到上述位置时：（发生不匹配）

发现公共前后缀为A，于是移动公共前后缀到下面位置：

为什么能够保证移动时就不会出现再匹配的情况呢

因为这里可以采用反证的手段，如果在移动时出现匹配，则就说明公共前后缀与所确定的模式串的公共前后缀不同，这就产生矛盾了。

KMP算法的思考

核心代码

求next数组（这里next数组表示模式串的公共前后缀个数）

//获取字符串的部分匹配值表
    public static int[] kmpNext(String dest){
        int[] next = new int[dest.length()];
        next[0] = 0;
        for (int i = 1, j = 0; i < dest.length(); i++) {//j可以代表匹配时的一个计算变量
            if(dest.charAt(i) == dest.charAt(j)) {
                j++;
            }else{
                j = next[j - 1];//如果出现匹配不成功则直接赋值0
            }
                next[i] = j;//找到i对应的j值，比如第一个字母A就是1，AB就是2
        }
        return next;
    }

求KMP算法：

public static int kmpSearch(String str1,String str2,int[] next){
        for (int i = 0,j = 0; i < str1.length(); i++) {//这里使用两个指针进行匹配
            while(j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j - 1];//这里是核心中的核心
            }
            if(str1.charAt(i) == str2.charAt(j)){
                j++;//指针前移
            }
            if(j == str2.length()){
                return i - j + 1;//这加个1是因为考虑到索引问题
            }
        }
        return -1;
    }

原文地址：http://www.cnblogs.com/robyn2022/p/16913210.html