KMP算法的深入理解与另一种写法

发表于 | 更新于 | 阅读次数：

这次再看KMP算法，学习资料主要是OI-Wiki和b站的一个讲解视频。

前缀函数

每当学到KMP的时候，总会听起什么next数组，这个东西其实就是前缀函数。

前缀函数定义

给定一个长度为n的字符串s，其前缀函数被定义为一个长度为n的数组next。（注意代码里的数组名不要起next，可能冲突）其中next[i]为既是子串s的前缀同时也是该子串的后缀的最长真前缀（proper prefix）长度。一个字符串的真前缀是其前缀但不等于该字符串自身。(转自OI-wiki 前缀函数与KMP算法)OI Wiki里已经写的很详细啦，这里就不再复读了，对前缀函数不够明白的，可以点击查看).

匹配

一般的方法呢，都是把next数组求出后，对文本串进行匹配。这种方法不再赘述。有趣的是，OI-Wiki中给出了一种仅对字符串求一次前缀函数进行匹配的方法，下面简单介绍一下这种写法。为了简便，用n表示模式串s的长度，用m表示文本text的长度。我们在s后加上一个符号，这个符号在两个串都不存在，之后把text拼接到s后边，这时候求s的前缀函数。很容易知道，当前缀函数值为n时，原模式串在文本中就出现了一次。
下面给出HDU-1686（裸的KMP匹配）的代码。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h> 
#include <string.h>
#include <vector>
using namespace std;
const int maxn=1011000;
char s[maxn],text[maxn]; 
int pre[maxn],n;
void prefix_function()  //求前缀函数
{
    for (int i = 1; i < n; i++)
    {
        int j = pre[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pre[j - 1];
        if (s[i] == s[j])
            j++;
        pre[i] = j;
    }
}
int main()
{
    int t,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s,text);
        int len=strlen(s) , ans=0;
        strcat(s,"#");
        strcat(s,text);
        n=strlen(s);

        prefix_function();
        for(int i=0 ;i<n ;i++)
        {
            if(pre[i]==len)
            	ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

一般匹配方法

注意注意：之前求出的前缀函数为什么可以加速匹配呢？因为它记录了模式串中既是前缀也是后缀的子串长度。最重要的是，我们得到的是数组，其中包含了模式串中以第一个字符开始，第i个字符结尾的子串的最长真前缀。举例来说，字符串 abcabcd 的前缀函数为 0 0 0 1 2 3 0 ，字符串 aabaaab 的前缀函数为 0 1 0 1 2 2 3。
由此很自然可以联想到这种常见的匹配方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <stdio.h> 
#include <string.h>
using namespace std;
const int maxn=1011000;
char s[maxn],text[maxn]; 
int pre[maxn];
void prefix_function(int n)  //求前缀函数
{
    for (int i = 1; i < n; i++)
    {
        int j = pre[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pre[j - 1];
        if (s[i] == s[j])
            j++;
        pre[i] = j;
    }
}
int main()
{
    int t,i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s%s",s,text);
        int n=strlen(s),ans=0;
        int m=strlen(text);
        prefix_function(n);

        int i=0,j=0;
        while(i<n && j<m)
        {
            if(s[i]==text[j])
            {
                i++;
                j++;
                if(i==n)
                {
                    ans++;
                    i=pre[n-1];//跳回上次匹配到的地方，而不是模式串起点
                }
            }
            else 
            {
                if(i)
                    i=pre[i-1];//跳回上次匹配到的地方，而不是模式串起点
                else 
                {
                    j++;
                }
            }
            
        }
        printf("%d\n",ans);
    }
    return 0;
}

笔者水平有限，若有错误，还望指正。邮箱：1337233082@qq.com

0%