你所不知道的 KMP 冷知识

ACM算法日常

发布于 2021-08-10 16:10:16

8580

发布于 2021-08-10 16:10:16

文章被收录于专栏：ACM算法日常

KMP 这个名字是由三个人名构成的，你知道吗？

KMP算法由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。

和AC自动机类似的，KMP算法也是一种字符串匹配算法。

只不过KMP适用于单模式串的匹配。而且KMP的next数组应用非常玄学。

可以发现，对于简单的字符串匹配算法，时间大规模的浪费在了重复的比较匹配上面，那么KMP算法用巧妙的预处理将重复的比较省去了。

如下图，在匹配到第六个字符，出现错误，而已经有了

个匹配字符的信息，我们可以根据这个信息，推知

s+1

的偏析是无效的，而

s+2

的偏移是会有三个字符匹配的，只要从第四个字符开始比较即可。

前缀函数

那么，我们和AC自动机类似的，我们需要知道失配以后的偏移情况。也就是这里的

\pi[i]

。简单来说

\pi[i]

就是，子串

s[0\dots i]

最长的相等的真前缀与真后缀的长度。

用数学语言描述如下：

\pi[i] = \max_{k = 0 \dots i}{k: s[0 \dots k - 1] = s[i - (k - 1) \dots i]}

特别地，规定

\pi[0]=0

。

举例来说，对于字符串 abcabcd，

\pi[0]=0

，因为 a 没有真前缀和真后缀，根据规定为 0

\pi[1]=0

，因为 ab 无相等的真前缀和真后缀

\pi[2]=0

，因为 abc 无相等的真前缀和真后缀

\pi[3]=1

，因为 abca 只有一对相等的真前缀和真后缀：a，长度为 1

\pi[4]=2

，因为 abcab 相等的真前缀和真后缀只有 ab，长度为 2

\pi[5]=3

，因为 abcabc 相等的真前缀和真后缀只有 abc，长度为 3

\pi[6]=0

，因为 abcabcd 无相等的真前缀和真后缀

同理可以计算字符串 aabaaab 的前缀函数为

[0, 1, 0, 1, 2, 2, 3]

。

模版

下面的字符串，我们都假设主串长度为

，模式串的长度为

显然，一个偏移位置就是以

为结尾的后缀和模式串前缀的极大匹配量，我们可以

O(m)

预处理出来。

需要注意的是，Next数组要比字符串多一位，最后一位表示的是全部匹配以后的偏移。

    void Pre_KMP()
    {
        for (int i=0;i<=m;i++)
            Next[i]=0;
        int j=0,k=-1;
        Next[0]=-1;
        while(j<m)
        {
            if (k==-1||t[j]==t[k]) Next[++j]=++k;
            else k=Next[k];
        }
    }

得到了偏移数组，匹配算法就比较显然了。

两个参数

和

分别是主串和模式串

int KMP(char *S,char *T)
{
    int i=0,j=0;
    while(i<n&&j<m)
    {
        if(j==-1||S[i]==T[j]) i++,j++;
        else j=Next[j];
    }
    if(j==m) return i-m;
    else return -1;
}

由此可知，KMP算法的预处理时间复杂度是

O(m)

，匹配的时间复杂度是

O(n)

，所以总的时间复杂度就是

O(n+m)

。

完全的匹配已经没有什么讲的意义了。我们来看一看Next数组的应用。

例题

HDU3336 Count the string

http://acm.hdu.edu.cn/showproblem.php?pid=3336

分析

前缀匹配成功的次数，我们可以利用Next数组。

根据Next数组的性质知，当Next数组有值的时候，就证明肯定有一个匹配，所以我们需要统计出Next数组里面

的个数

但是一个

Next数组位贡献可能不止1，因为他本身后缀的前缀可能也是一个符合要求的

所以我们对于每一个

Next数组位需要向前探查有多少符合要求的前缀，就是他的贡献个数

再加上与自身的匹配

就是答案

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f
#define P pair<int,int>

using namespace std;

int T,n,m,ans,Next[200010];
char x[200010];

void Pre_KMP()
{
    for (int i=1;i<=n;i++)
        Next[i]=0;
    int j=0,k=-1;
    Next[0]=-1;
    while(j<n)
    {
        if (k==-1||x[j]==x[k]) Next[++j]=++k;
        else k=Next[k];
    }
}

void dfs(int x)
{
    if (x==0||x==-1) return ;
    ans++;ans%=10007;
    dfs(Next[x]);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        scanf("%s",x);
        Pre_KMP();
        ans=n%10007;
        for (int i=0;i<n;i++)
            dfs(Next[i]);
        printf("%d\n",ans);
    }
    return 0;
}

ZOJ1905 Power Strings

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1905

分析

Next数组的经典应用，求最短的循环节，可以得到是

len-Next[len]

。

那么存在循环节的条件自然就是，

len

能够整除

len-Next[len]

。

证明就略了。直观感受以下也不难。

POJ2752 Seek the Name, Seek the Fame

http://poj.org/problem?id=2752

分析

显然

S_1,\cdots ,S_{Next[i]}

和

S_{len-Next[i]+1},\cdots ,S_{len}

是最长公共前后缀

显然

S_1,\cdots ,S_{Next[Next[i]]}

和

S_{len-Next[Next[i]]+1},\cdots ,S_{len}

也是公共前后缀

如此反复的话，我们直接递归调用即可。

别忘了自己本身也是公共前后缀。

NOI2004 动物园

题意

对于字符串

的前

个字符构成的子串，既是它的后缀同时又是它的前缀，并且该后缀与该前缀不重叠，将这种字符串的数量记作

num[i]

。求

\prod_{i=1}^L (num[i]+1)\; mod\; 1000000007

。

分析

利用性质：

Next[i]

表示

i-1

为结尾的字符串的最长公共前后缀（不算本身）

可以得到，满足要求的数量就是不断的跳

Next[x]

，但是要保证

x\le \frac{y}{2}

，

为当前位置，

为前缀的结束位置。

但是直接这样跳复杂度不对，题目要求的复杂度是

O(|S|)

的。

我们考虑

num[x]

的计算方式，利用上面的分析可以知道，如果不考虑互相重叠的话，

num[x]=num[Next[x]]+1

。

显然

num

数组是递增的。那么考虑重叠的时候，显然

num'[x]

的值是嵌套的

中，满足比

\le

一半的最后一个位置。

我们可以用类似于kmp匹配的方法。

如果当前位置

像后移动一位，那么他所对应的答案最多也是向后移动一位。

所以，如果当前指向的位置为

，如果能匹配上则继续匹配下一位，当前的答案为

num[k]

，如果匹配失败就往前跳；另一种情况是，当前的

k>\frac{x}{2}

（

是当前的位置）了，那么也是往前跳。

#include<bits/stdc++.h>
#define LL long long
#define inf 0x3f3f3f3f

using namespace std;

struct kmp
{
    char t[1000010];
    int Next[1000010],m;
    void Pre_KMP()
    {
        for (int i=0;i<=m;i++)
            Next[i]=0;
        int j=0,k=-1;
        Next[0]=-1;
        while(j<m)
        {
            if (k==-1||t[j]==t[k]) Next[++j]=++k;
            else k=Next[k];
        }
    }
}K;

int T,n;
LL num[1000010];
char s[1000010];
const LL mo=1000000007LL;

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s",K.t);
        K.m=strlen(K.t);
        K.Pre_KMP();
        LL ans=1;
        num[0]=0LL;
        for (int i=1;i<=K.m;i++)
            num[i]=num[K.Next[i]]+1LL;
        int k=0;
        for (int i=1;i<=K.m;i++)
        {
            while(k&&K.t[k]!=K.t[i-1]) k=K.Next[k];
            if (K.t[k]==K.t[i-1]) k++;
            while(k>i/2) k=K.Next[k];
            ans=ans*(num[k]+1LL)%mo;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

总结常见（奇怪）的应用

以下均指开始下标为

的字符串

长度为

len

字符串的最短循环节长度为

len-Next[len]

Next[i]

表示

i-1

为结尾的字符串的最长公共前后缀（不算本身）

前缀

的最长循环节长度为

i-f[i]

(不算本身)

for (int i=1;i<=K.m;i++)
    if (K.Next[i]==0) f[i]=i;
    else f[i]=f[K.Next[i]];

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-08-08，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

http

本文分享自 ACM算法日常微信公众号，前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

http

登录后参与评论

0 条评论

热度