什么是KMP算法

Knuth-Morris-Pratt算法（简称KMP）是常用的字符串匹配算法之一。

假设现在有一个模式串a="ABACABAD"和一个主串b="BBC ABACABACABAD ABCDABDE"，要判断主串b是否包含模式串a，如果包含，则返回出模式串在主串的位置下标。

易知使用暴力匹配算法的时间复杂度为O(m*n),其中m和n为模式串和主串的长度。而使用KMP算法，则能在线性时间O(m+n)中完成匹配工作。

KMP算法实现逻辑

使用暴力匹配算法时，每次不匹配，都需要从主串下一个位置从头匹配一次模式串，这种回溯工作，导致效率低下。KMP算法核心思想是充分利用上次不匹配时的计算结果，避免"一切重新开始"的计算工作。

以下通过一个简单的例子进行说明：

1、首先，使用主串的第一位与模式串的第一位进行比较，如果不同，则将主串的第二位与模式串的第一位进行比较，以此类推。

比较主串第一位与模式串第一位的字符比较主串第二位与模式串第一位的字符

2、直到主串有一个字符与模式串的第一位相同，则比较主串下一个位置的字符，是否与模式串的第二位相同，以此类推。

主串中的字符匹配到模式串的第一位字符比较主串的下一个字符与模式串的第二位字符

3、当匹配到某个位置，主串与模式串的字符不同时，此时不直接从主串下一个位置，再从头逐个比较。因为在比较过程中，我们可以知道两个细节：

（1）模式串的前面部分的字符串内容是与主串的部分字符是相同的。

（2）在该模式串"ABACABAD"中，下标0~2的字符是与下标4~6的字符是相同的。

因此，我们直接使用下标位置为3的字符与主串进行比较，这样就能大大提高效率了。

主串字符C与模式串D不匹配模式串下标0~2的字符是与下标4~6的字符相同，因此也与主串的前三个位置的字符是匹配的不重头开始比较，而是比较模式串下标3的字符与主串中的字符是否相同

4、以此类推，直到匹配到模式串的最后一位，或者扫描完主串。

匹配到模式串的最后一位

部分匹配表

在匹配步骤3中，其实利用了模式串本身字符的组合顺序信息，在KMP算法中，我们需要将该字符组合顺序信息记录起来，称之为"部分匹配表"。

"部分匹配表"是如何产生的呢？首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符，一个字符串的全部头部组合,"后缀"指除了第一个字符，一个字符串的全部尾部组合。

例如字符串a="ABCAB"，前缀字符串集合为[A, AB, ABC,ABCA]，后缀字符串集合为[B, AB, CAB,BCAB]，可以看到前缀和后缀有相同的子串[AB]。

部分匹配值，其实就是计算出下标在0~i的子字符串中(i<=a.length)，前缀与后缀最长相同子串的长度。

"部分匹配表"计算规则可参考阮一峰老师的日志“字符串匹配的KMP算法”。

我们根据这个规则，可计算模式串a="ABACABAD"的部分匹配表，如下：

KMP算法的JAVA 代码实现

1.计算部分匹配值。

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;
}

代码说明：

1）声明部分匹配表数组，用于存储匹配值。

2）当字符串为空字符串str="",没有前后缀字符串，因此最长匹配值为0，next[0] = 0。

3）循环字符串，计算出下标在0~i的字符串的部分匹配表，i初始化为1。j用于记录前缀与后缀最长相同子串的长度。

(a) 如果在0~i的子字符串，j=0，并且dest.charAt(j) != dest.charAt(i)时，表示在0~i这一段中，前后缀字符串集合中没有相同字符串，因此next[i]=j（即next[i]=0）。

(b) 如果在0~i的子字符串，j=0，dest.charAt(j) == dest.charAt(i)时，表示在0~i这一段中，前后缀字符串集合中有一个字符串相同，因此j++;next[i]=j;（即next[i]=1）。

(c) 如果在0~i的子字符串，dest.charAt(j) == dest.charAt(i)时，如果j>0，则表示上一轮比较，在0~i-1的子字符串中，前缀与后缀有相同子串。因此在0~i这一段中，前缀与后缀也有相同子串，并且最长的共有字符串长度为j++。因此j++;next[i]=j。

(d) 如果在0~i的子字符串，j>0，dest.charAt(j) != dest.charAt(i)时，则表示上一轮比较时，字符串[0~j-1]是字符串[0~i-1]中，前后缀的最长相同字符串，如果我们找到在字符串[0~j-1]中的最长前后缀相同字符串(记作maxComStr)，继续比较maxComStr下一位与dest.charAt(i)，则能减少比较次数。通过部分匹配表中可见，next[j-1]为[0~j-1]中前后缀最长相同字符串的长度，我们也可以理解为是最长相同字符串下一个字符的下标，因此j=next[j-1]，举例说明：

dest.charAt(j) != dest.charAt(i)字符串[0~j-1]中，前缀字符串集合为[A,AB]，后缀字符串集合为[A,BA],最长共有元素为A,j=next[j-1],则j移动到了该最长前缀字符串下一位继续比较该最长前缀字符串下一位与dest.charAt(i)

2.比较模式串和主串。

public static int kmp(String str, String dest){
    //1.首先计算出部分匹配表
    int[] next = kmpnext(dest);
    //2.查找匹配位置
    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 -1;
}

代码说明：

1）计算部分匹配表。

2）j为模式串a下标，i为主串b下标。循环主串，查找匹配位置。

(1) 如果j=0，并且str.charAt(i) != dest.charAt(j)时，则移动主串下标位置，比较主串下一位字符是否与模式串第一位字符相同。

(2) 如果str.charAt(i) == dest.charAt(j)时，则同时移动主串下标位置和模式串下标位置，依次比较下一位。

(3) 如果比较到模式串某个位置(j>0)，str.charAt(i) != dest.charAt(j)时，则根据部分匹配表，移动到[0~j-1]字符串的前后缀最长相同字符串的后一位，继续进行比较。如在该模式串dest ="ABACABAD"中，当j=7时，dest.charAt(7)与主串的字符不同。而dest[0~6]这部分字符串是与主串str[i-6~i-1]匹配的，dest[0~2]字符是与dest[4~6]的字符是相同的，由此可以推断出dest[0~2]的字符也与主串str[i-3~i-1]的字符是相同的。通过部分匹配表中可见，next[j-1]为前后缀最长相同字符串的长度，我们也可以理解为是最长相同字符串下一个字符的下标，因此j=next[j-1]。

(4) 当j == dest.length()时，表明完成模式串的比较，返回匹配起始位置(i-j+1)。

完整代码如下：

public class Kmp {

    public static void main(String[] args){
        String a = "ABACABAD";
        String b = "BBC ABACABACABAD ABCDABDE";
        int result = kmp(b, a);

        //打印结果：和字符串获得匹配的位置        System.out.println("resultPosion:"+result);
    }

    /**     * KMP 匹配     */
    public static int kmp(String str, String dest){
        //1.首先计算出 部分匹配表        int[] next = kmpnext(dest);

        System.out.println("next ="+Arrays.toString(next));
        //2.查找匹配位置        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 -1;
    }

    /**     * 计算部分匹配表     */
    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;
    }}