浅谈KMP算法

KMP是什么？

Knuth-Morris-Pratt（简称KMP）是一种高效的字符串匹配算法，用来在主字符串中查找模式字符串（子字符串）的位置，例如在主串"Hebei Normal University" 中查找模式串"University"的位置。

这个算法是由D.E.Knuth和V.R.Pratt在1974年构思，同年J.H.Morris也独立设计出该算法，最终三人于1977年联合发表。KMP这个名字则取自三人姓氏首字母。

KMP有什么用？

字符串匹配

朴素的暴力匹配的时间复杂度是 $O(n*m)$ 。

而KMP可以高效的在 $O(m + n)$ 的时间复杂度下完成字符串模式匹配，其中 $m$ 和 $n$ 分别是主串和模式串的字符长度。

KMP怎么用？

KMP的思想核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。

首先要明白三个概念：前缀、后缀以及部分匹配值。

前缀：字符串中除了最后一个字符以外，其余字符的全部头部顺序组合。

例如"abcab"的前缀为"a",“ab”,“abc”,“abca”。

后缀：字符串中除了第一个字符以外，其余字符的全部尾部顺序组合。

例如"abcab"的后缀为"b",“ab”,“cab”,“bacb”。

部分匹配值：前后缀相同元素长度。

例如"abcab"的最大部分匹配值为2，即"ab"。

大致思路

以在S主串"ababcabcacbab"中查找P子串"abcac"为例。

kmp0

第一次匹配到的第6个字符时遇到不匹配的情况，此时主串S中已经匹配的字符串为"ababa"，子串P中已经匹配的字符串自然也为"ababa"。

kmp1

观察可发现S串中的后三个字符与P串中的前三个字符是相同的。

kmp2

所以将字串和主串的相同后缀对齐。

kmp3

如此，便找到了字串P在主串S中出现的位置。

通过这个样例可以看出，每次滑动的位数是（已匹配字符串长度 - 最大部分匹配值），滑动位数与主串无关，仅通过模式串即可求出，由此引出next数组，即用next数组存储当模式串中第i个字符不匹配时应该移动的位数。

next数组

next数组可谓是KMP算法的核心。

例如求"ababa"的next数组

字符串	next数组下标	next数组值	最大部分匹配部分
无	0	0	无
a	1	0	无
ab	2	0	无
aba	3	1	a
abab	4	2	ab
ababa	5	3	aba

所以说next数组就是求一个字符串的最大部分匹配值

next数组手算（部分匹配）

在前面已经了解过前缀、后缀和部分匹配值的概念。

以ababa为例：

a的前缀和后缀都为空集，最长相等前后缀长度为0
ab的前缀为{a}，后缀为{b}，{a}∩{b} = Ø，最长相等前后缀长度为0.
aba的前缀为{a,ab}，后缀为{b,ba}，相交等于{a}，最长相等前后缀长度为1.
abab的前缀为{a,ab,aba}，后缀为{b,ab,bab}，相交等于{ab}，最长相等前后缀长度为2.
ababa的前缀为{a,ab,aba,abab}，后缀为{a,ba,aba,baba}，相交等于{a,aba}，最长相等前后缀长度为3.

因此这个字符串的部分匹配值为00123.

于是，部分匹配值的表如下：

下标	1	2	3	4	5
字符	a	b	a	b	a
值	0	0	1	2	3

将这个表的值右移一位，首位补-1，溢出的舍去，得到如下表：

下标	1	2	3	4	5
字符	a	b	a	b	a
值	-1	0	0	1	2

这个表就是next表

有时为了使公式更加简洁、计算简单，将next数组整体+1.因此，上述表也可以写成下表所示。

下标	1	2	3	4	5
字符	a	b	a	b	a
值	0	1	1	2	3

next数组手算（公式）

kmp公式

next数组代码

for(int i = 2, j = 0; i <= m; i++) {
    while(j && p[i] != p[j+1]) j = next[j];
    if(p[i] == p[j+1]) j++;
    next[i] = j;
}

上述代码与《数据结构》课本中有所不同，请注意。

完整KMP代码为：

#include<iostream>

using namespace std;

const int N=100010,M=1000010;

char q[N],s[M];

int ne[N];//保存next数组

int main()
{
    int n,m;

    cin>>n>>q+1>>m>>s+1;//下标均从1开始

    for(int i=2,j=0;i<=n;i++)
    //j表示匹配成功的长度,i表示q数组中的下标,因为q数组的下标是从1开始的,只有1个时,一定为0,所以i从2开始
    {
        while(j&&q[i]!=q[j+1]) j=ne[j];
        //如果不行可以换到next数组
        if(q[i]==q[j+1]) j++;
        //成功了就加1
        ne[i]=j;
        //对应其下标
    }
    //j表示匹配成功的长度,因为刚开始还未开始匹配,所以长度为0
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&s[i]!=q[j+1]) j=ne[j];
        //如果匹配不成功,则换到j对应的next数组中的值
        if(s[i]==q[j+1]) j++;
        //匹配成功了,那么j就加1,继续后面的匹配
        if(j==n)//如果长度等于n了,说明已经完全匹配上去了
        {
            printf("%d ",i-j);
            //因为题目中的下标从0开始,所以i-j不用+1;
            j=ne[j];
            //为了观察其后续是否还能跟S数组后面的数配对成功
        }
    }

    return 0;
}