KMP 字符串匹配

来补一下。

1.KMP 字符串匹配

KMP 常用来求单文本串与单模式串的匹配问题。大致分为两步，求出前缀函数与进行匹配。下面分别介绍。

1.1.前缀函数

第一步：求出模式串的前缀函数。

先介绍 Border 的概念，对于字符串 $s[1\dots n]$，所有满足 $s[1\dots i]=s[n-i+1 \dots n]$ 且 $i \neq 1$ 的前缀为 $s[1\dots n]$ 的一个Border。

字符串 $s[1 \dots n]$ 的前缀函数 $\pi[i]$ 定义为字串 $s[1 \dots i]$ 的最长 Border 的长度，不存在任何 Boder 时值为 $0$。

1.1.1.性质

$(1)$.若 $s[\pi[i]+1]=s[i+1]$ ，则 $\pi[i+1]=\pi[i]+1$。

$(2)$.$s[1 \dots i]$ 的 Border 的 Border 是 $s[1 \dots i]$ 的 Border。

$(3)$.$s[1 \dots i]$ 的 Border 集合为 $s[1\dots \pi[i]],s[i\dots \pi[\pi[i]]],\cdots$。

通过性质 $(2)$ 以及 $\pi[i]$ 的最长性，通过反证法容易得到性质 $(3)$。

1.1.2.计算

假设当前情况下，我们根据上面三条性质来求尝试计算 $\pi[i+1]$ 。

根据性质 $(2)$，我们只需要将 $s[i+1]$ 与 $s[1 \dots i]$ 所有 Border 的后面一位进行匹配即可。根据性质 $(3)$，我们在适配时不断将 $i$ 跳到 $\pi[i]$ 即可遍历所有后缀。再根据性质 $(1)$，这样即可求出 $\pi[i+1]$。

这样的是时间复杂度是多少？设 $j$ 为之前已匹配的最大长度，即 $\pi[i]$。注意到 $j$ 每一次最多只能增加 $1$ ，那么 $j$ 的增量最多为 $n$，所以失配时跳到 $\pi[i]$ 的次数为 $\mathcal O(n)$。于是时间复杂度为 $\mathcal O(n)$。

模板

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

1.2.匹配

第二步：在文本串中进行匹配。

通过上一步的过程，我们已经可以看到，KMP 核心思想是 利用之前匹配好的信息，就是与之匹配的 Border，继续进行匹配。而在第二部中也是如此。我们还是利用不停地跳 $\pi[i]$ 遍历 $s[1 \dots i]$ 的所有 Border，与上面的过程十分相似，此处不再赘述。

模板

for(int i=1,j=0;i<=n;i++)
{
    while(j&&s[i]!=t[j+1])j=ne[j];
    if(s[i]==t[j+1])j++;
    // if(j==m)printf("%d\n",i-m+1);
}

1.3.应用

我们发现前缀函数 $\pi[i]$ 有一些很好的性质，于是衍生出更多的应用。下面是一些简单的例子。

1.UVA1328 Period

经典问题，求一个字符串的所有前缀的最大周期长度。仔细观察，设存在 $s[1 \dots j]$ 为 $s[1 \dots i]$ 的最小周期，其充要条件是 $j|i$ 且 $j=i-\pi[i]$。也比较好证明。画个图更好理解。于是我们只需要求一遍 $\pi[i]$ 即可。

2.P3435 [POI2006] OKR-Periods of Words

设 $s[1 \dots j]$ 为 $s[1 \dots i]$ 的长度最小的一个 Border，容易发现 $s[i-j+1 \dots i]$ 的长度即为所求。于是不停跳 $\pi[i]$ 找到最短的 Border 长度即可。但是对于每一个子串暴力跳的话 $j$ 的变化次数是 $\mathcal O(n^2)$ 的，时间复杂度也是 $\mathcal O(n^2)$ 的。考虑一个小优化，我们每次跳完 就将 $\pi[i]$ 赋为 $j$，注意到 Border 之间是呈现一个树形结构，于是这个优化可以类似于并查集的路径压缩，所以对于每个前缀最多只需要跳一次。这样做的时间复杂度就是 $\mathcal O(n)$。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10;
char s[N];
int n,ne[N];
long long ans;
int main()
{
    scanf("%d%s",&n,s+1);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1])j=ne[j];
        if(s[i]==s[j+1])j++;
        ne[i]=j;
    }
    for(int i=2,j=2;i<=n;i++,j=ne[i])
    {
        if(ne[j])j=ne[j];
        if(j)ne[i]=j,ans+=i-j;
    }
    printf("%lld\n",ans);
    return 0;
}

3.P3426 [POI2005]SZA-Template

不妨直接设记 $f_i$ 表示以 $i$ 结尾的字符串的答案。进行仔细观察，答案必须为字符串的一个 Border 或者字符串本身。更进一步地，答案只可能为 $f_{\pi[i]}$ 或者 $i$。因为不可能存在一个可以表示 $s[1 \dots i]$ 但无法表示 $s[1 \dots \pi[i]]$ 的 Border。这意味着结尾与前面部分最多只能接上 $s[1 \dots \pi[i]]$ 这一段，前面部分也需要有这个结构构成，于是我们要找到一个 $j$，满足 $f_j=f_{\pi[i]}$ 且 $i-j \le \pi[i]$，那么其值为 $f_{\pi[i]}$，否则为 $i$。这个过程可以用一个桶简单实现。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=5e5+10;
int n;
char s[N];
int ne[N],f[N],p[N];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=2,j=0;i<=n;ne[i]=j,i++)
    {
        while(j&&s[i]!=s[j+1])j=ne[j];
        if(s[i]==s[j+1])j++;
    }
    for(int i=1;i<=n;i++)p[f[i]=i-p[f[ne[i]]]<=ne[i]?f[ne[i]]:i]=i;
    printf("%d\n",f[n]);
    return 0;
}

2.Z 函数

Z 函数也称扩展 KMP，求法与 KMP 很类似。

2.1.定义

对于字符串 $s[1 \dots n]$，定义函数 $z[i]$ 表示 $s$ 与 $s[i\dots n]$ 的最长公共前缀 LCP 的长度，$z$ 被称为 $s$ 的 Z 函数。

2.2.求法

核心思想还是利用好之前已经匹配好的信息。我们设 $s[l\dots r]$ 是当前 $r$ 最大的一个匹配段，分为两种情况讨论：

• 如果 $i<r$，因为有 $s[i,r]=s[i-l+1,r-l+1]$，所以得到 $z[i]\ge \min (z[i-l+1],r-i+1)$。于是分为两种情况：
  • $z[i-l+1]<r-i+1$，直接令 $z[i]=z[i-l+1]$。
  • $z[i-l+1]\le r-i+1$，从 $r$ 开始暴力向右进行扩展。

具体实现如下：

模板

for(int i=2,l=0,r=0;i<=n;i++)
{
    if(i<=r)z[i]=min(z[i-l+1],r-i+1);
    while(i+z[i]<=n&&s[i+z[i]]==s[z[i]+1])z[i]++;
    if(i+z[i]-1>r)l=i,r=i+z[i]-1;
}

while 中每次向后扩展一位都至少会使 $r$ 增加 $1$，所以总共最多只会执行 $\mathcal O(n)$ 次，外层循环只有一层遍历。所以总的时间复杂度为 $\mathcal O(n)$。

同样类似于上一步以及 KMP 的匹配过程，Z 函数还可以用来求模板串与文本串的每一个后缀的 LCP 长度数组。这里不再赘述。

模板

for(int i=1,l=0,r=0;i<=n;i++)
{
    if(i<=r)p[i]=min(z[i-l+1],r-i+1);
    while(i+p[i]<=n&&s[i+p[i]]==t[p[i]+1])p[i]++;
    if(i+p[i]-1>r)l=i,r=i+p[i]-1;
}

2.3.应用

通过上面我们逐渐认识到前缀函数 $\pi[i]$ 与 Z 函数 $z[i]$ 是相似的。$\pi[i]$ 是以 $i$ 结尾，$z[i]$ 则是以 $i$ 开头。所以二者的应用也是类似的。但不同情况下的方便程度也不一样。

1.P8112 [Cnoi2021]符文破译

在这里看

2.P7114 [NOIP2020] 字符串匹配

经典题，不再赘述。

3.失配树

KMP 的小扩展，我们很容易发现根据前缀函数 $\pi[i]$ 发现 Border 之间呈现一个树形结构。于是关于一些关于 Border 的问题我们可以通过将这棵树具体地建出来，在进行处理，这棵树就是失配树。同时这个在 AC 自动机上也有应用。

1.P5829 【模板】失配树

模板题，按照上面所说，直接求 LCA 即可。

模板

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+10;
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m;
char s[N];
int pi[N];
int tot,head[N],ver[N],ne[N];
int d[N],si[N],son[N],fa[N],top[N];
inline void add(int u,int v)
{
    ver[++tot]=v;
    ne[tot]=head[u];
    head[u]=tot;
}

void dfs1(int x)
{
    si[x]=1;
    son[x]=-1;
    for(int i=head[x];i;i=ne[i])
    {
        int y=ver[i];
        d[y]=d[x]+1,fa[y]=x;
        dfs1(y);
        si[x]+=si[y];
        if(son[x]==-1||si[son[x]]<si[y])son[x]=y;
    }
}
void dfs2(int x,int t)
{
    top[x]=t;
    if(~son[x])dfs2(son[x],t);
    for(int i=head[x];i;i=ne[i])
        if(ver[i]!=son[x])
            dfs2(ver[i],ver[i]);
}
int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(d[top[x]]<d[top[y]])swap(x,y);
        x=fa[top[x]];
    }
    if(d[x]>d[y])swap(x,y);
    return x;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[j+1]!=s[i])j=pi[j];
        if(s[j+1]==s[i])j++;
        pi[i]=j;
    }

    pi[1]=0;
    for(int i=1;i<=n;i++)add(pi[i],i);
    
    dfs1(0);
    dfs2(0,0);
    read(m);
    while(m--)
    {
        int x,y;
        read(x,y);
        printf("%d\n",LCA(fa[x],fa[y]));
    }
    return 0;
}

应用感觉也不多，不太找得到。但上面很多题目都可以用失配树完成。