字符串匹配的KMP算法介绍 和 Java代码的实现

算法介绍

1、 算法作用

用于判断一个source字符串中是否包含一个特定的模式串，并返回最早出现的位置，还可用于其他用法，如出现几次等
例：
字符串”BBC ABCDAB ABCDABCDABDE” 中是否含有字符串”ABCDABD”

2、相比暴力解决方法

kmp方法算法就利用之前判断过信息，通过一个next数组《部分匹配表》，不用把source字符串的”搜索位置”移回已经比较过的位置，而是往后移动模式串当前的比较位置，这样就提高了效率
移动位数 = 已匹配的字符数 - 对应的部分匹配值

3、部分匹配表

“部分匹配”的实质是，有时候，字符串头部和尾部会有重复。比如，”ABCDABD”之中有两个”AB”，那么它的”部分匹配值”就是2（”AB”的长度）。搜索词移动的时候，第二个”AB”向后移动4位（字符串长度-部分匹配值），就可以来到第一个”AB”的位置。

匹配表的实现：

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例

－　"A"的前缀和后缀都为空集，共有元素的长度为0；

－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

使用Java实现算法

public class KMP {
   //用于计算匹配的位置（从头到尾）
    public static int kmp(String str, String dest,int[] next){//str文本串 dest 模式串
        for(int i = 0, j = 0; i < str.length(); i++){
            while(j > 0 && str.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            if(str.charAt(i) == dest.charAt(j)){
                j++;
            }
            if(j == dest.length()){
                return i-j+1;
            }
        }
        return 0;
    }
    //用于生成部分匹配表
    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++){
            while(j > 0 && dest.charAt(j) != dest.charAt(i)){
                j = next[j - 1];
            }
            if(dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    //测试用例
    public static void main(String[] args){
        String a = "ababa";
        String b = "ssdfgasdbababa";
        int[] next = kmpnext(a);
        int res = kmp(b, a,next);
        System.out.println(res);
        for(int i = 0; i < next.length; i++){
            System.out.println(next[i]);            
        }
        System.out.println(next.length);
    }
}

参考：https://blog.csdn.net/christ1750/article/details/51259425
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html