KMP

对于模式串的常规匹配算法通常时间复杂度很大，效率不高。因此 D. E. Knuth 与 V. R. Partt 和 J. H. Morris 同时发现了一种改进算法，称之为Knuth-Partt-Morris 算法，简称 KMP 算法。此算法的时间复杂度可以达到 $O(m+n)$。

在 KMP 算法中最为重要的就是得到前缀表Prefix table，用来存储在不同位置上匹配失败时子串后移的距离，用一个一维数组表示(数组的实际存储下标从1开始)。
模式串：

A	B	A	B	A	B	B

用该模式串来匹配主串时，存在7个不同位置的匹配失败，得到下列几种子串(最后一个字母匹配失败)：

A	B	A	B	A	B	B
A
A	B
A	B	A
A	B	A	B
A	B	A	B	A
A	B	A	B	A	B
A	B	A	B	A	B	B

子串头开始的子串为前缀，不匹配处往前的子串称之为后缀，当该字串的最大公共前缀等于其最大公共后缀时得到的公共子串称之为最大公共最大子串。
以上7种子串的最大公共子串分别是(0 表示没有)：

0	0	0	A	AB	ABA	ABAB

这7种子串的最大公共子串长度分别是:

0	0	0	1	2	3	4

在不匹配时，将公共前缀移到公共后缀位置，也就是最大公共子串的长度+1，即可得到前缀表Prefix table

0	1	1	2	3	4	5

用C/C++代码描述

int getnext(Str substr, int next[]){

    int i = 1, j = 0;
    next[j] = 0;
    while(i < substr.length){
        if(j == 0 || substr.ch[i] == substr.ch[j]){
            // j == 0 保证了next[i]的值一定大于等于1，因为这个数组下标从1开始
            i++;
            j++;
            next[i] = j;
        }
        else 
            j = next[j];
            // 这里使用了动态规划进行优化，也可以使用常规方法，j--;
    }
    return 0;
}

KMP的优化

尽管上述方法已经大幅减少匹配时间，但是在遇到特殊的模式串时，根据next[j]回溯时可能存在重复，比如模式串：

A	A	A	A	A	B
0	1	2	3	4	5

当前比较位置假设为 j，当 j=5 时，字符不匹配，通过 next[j]=4 来时 j 回溯到 4 的位置，但是 j=4 时的字符和 j=5 的字符一样，继续回溯，next[j]=3，同样仍然要继续回溯，这使得 j 的值要在 5，4，3，2，1的位置依次回溯，这些的位置上的字符都是相等的，所以可以通过改进算法，使得 j 的回溯直接跳到最先的相同字符串位置。nextval 数组来保存更新的next 数组。

以模式串ABABAAB为例，求得其 next 和 nextval 数组

A	B	A	B	A	A	B

根据前面的 KMP 算法，容易得到其 next 数组：

0	1	1	2	3	4	5

求 nextval 数组的一般方法：

1. 当 j 等于 1 时，nextval[j]=0，作为特殊标记。
2. 当 $p_j$ 不等于 $p_k$ 时（k 等于 next[j]），nextval[j] 被赋值为 k。
3. 当 $p_j$ 等于 $p_k$ 时（k 等于 next[j]），nextval[j] 被赋值为 nextval[k]。

由此得到 nextval 数组：

0	1	0	1	0	4	1

直接修改 getnext 函数，得到 getnextval 函数

int getnext(Str substr, int nextval[]){

    int i = 1, j = 0;
    nextval[j] = 0;
    while(i < substr.length){
        if(j == 0 || substr.ch[i] == substr.ch[j]){
            i++;
            j++;
            if(substr.ch[i] != substr.ch[j])
                nextval[i] = j;
            else 
                nextval[i] = nextval[j];
        }
        else 
            j = nextval[j];
    }
    return 0;
}