KMP 学习笔记

· · 算法·理论

OI-wiki 上的内容。

这是学长讲的内容，我又重新整理了一遍。保证简单易懂。

字符串的若干记号

举例：

将 s=\texttt{abcababc} 代入下面的程序中。

算法推导

先不用管怎么匹配，考虑求 fail 怎么做。

首先显然有暴力求 fail 的算法：枚举每个 1\le j<i\le n，判断 pre(j)=s[i-j+1,i]，若满足则将 fail(i) 与 j 比较并更新。

注意，在本文代码中所有字符串下标都从 0 开始！

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct Hash{
    const ll M=1e9+97;
    const ll B=131;
    string s; 
    int len;
    ll pw[N],hsh[N];
    void pre(){
        len=s.size(),pw[0]=1,hsh[0]=s[0];
        for(int i=1;i<=len;i++) pw[i]=pw[i-1]*B%M;
        for(int i=1;i<=len;i++) hsh[i]=(hsh[i-1]*B+s[i-1])%M;
    }
    ll qry(int l,int r){
        return (hsh[r]-hsh[l-1]*pw[r-l+1]%M+M)%M;
    }
};
int fail[N];
int main(){
    Hash h1;
    cin>>h1.s;
    h1.pre();
    int n=h1.len;
    for(int i=1;i<=n;i++){
        printf("border of pre(%d):",i);
        for(int j=1;j<i;j++)
            if(h1.qry(1,j)==h1.qry(i-j+1,i)) 
                printf(" %d",j),fail[i]=j;
        puts("");
    }
    for(int i=1;i<=n;i++) printf("%d ",fail[i]);
    return 0;
}

这是平方级别的，于是考虑优化。先来推到 fail 的几个性质：

这个非常显然。比如 s=\texttt{abab}，这时 bd(s)=\{2\}，在 i=1 时，前面的 pre(1) 比 pre(2) 少了末尾，而后面的 suf(1) 比 suf(2) 少了开头。

其实也非常显然。l\in bd(s) 根据定义即为 pre(l)=suf(l)，所以 s[1,l]=s[n-l+1,n]，所以将两个字符串同时去掉最后一个字符得到 s[1,l-1]=s[n-l+1,n-1]，即可证明 l-1\in bd(pre(n-1))。

其实也不难理解。左边的一坨就是 bd(pre(x)) 里面所有元素都减一。假设 l\in bd(pre(x))，根据定义，s[1,l]=s[x-l+1,x]。按照上一条性质，都删掉末尾字符，可得 s[1,l-1]=s[x-l+1,x-1]。那么 l-1 一定满足右边一坨，即 s[1,l-1]=s[(x-1)-(l-1)+1,(x-1)]，所以对于 pre(x-1) 来说 pre(i-1)=suf(i-1)。证毕。

举例，代入 s=\texttt{abaacbacabaa} 进上面的程序。略。

所以，判断 l 是 pre(x+1) 的 border，只需要从 l-1\in bd(pre(x)) 中枚举，然后依次判断即可。这样做优化了 j 的枚举范围。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
struct Hash{
    const ll M=1e9+97;
    const ll B=131;
    string s; 
    int len;
    ll pw[N],hsh[N];
    void pre(){
        len=s.size(),pw[0]=1,hsh[0]=s[0];
        for(int i=1;i<=len;i++) pw[i]=pw[i-1]*B%M;
        for(int i=1;i<=len;i++) hsh[i]=(hsh[i-1]*B+s[i-1])%M;
    }
    ll qry(int l,int r){
        return (hsh[r]-hsh[l-1]*pw[r-l+1]%M+M)%M;
    }
};
vector<int> bd[N];
int main(){
    Hash h1;
    cin>>h1.s;
    h1.pre();
    int n=h1.len;
    for(int i=1;i<=n;i++){
        if(i!=1&&h1.s[0]==h1.s[i-1]) bd[i].push_back(1);
        //注意特判长度为 1 的 boader。
        //此外还需要判断 i=1 时不符合 boader 定义中 i<n 的情况。你可以把 i!=1&& 去掉试试。
        for(int j:bd[i-1])
            if(h1.qry(1,j+1)==h1.qry(i-(j+1)+1,i)) 
                bd[i].push_back(j+1);
        printf("border of pre(%d):",i);
        for(int j:bd[i]) printf(" %d",j);
        puts("");
    }
    return 0;
}

再次优化，发现上一个代码中 h1.qry(1,j+1)==h1.qry(i-(j+1)+1,i) 中有些比较完全是多余的，由于 j\in bd(i-1)，已经有 s[1,j]=s[(i-1)-j+1]，只需比较 s_{j+1} 与 s_i 即可。

接下来还有一个很重要的优化。

一个简单一些的解释：bd(s) 中的元素，要么是 fail(n)，要么就是 bd(pre(fail(n)))。

这个其实也很显然：为了直观理解，下文令 x=fail(n)。考虑 l\neq x 且 l\in bd(s) 时，根据定义 l\in bd(s) 是 s[1,l]=s[n-l+1,n]。由于原串存在 s[1,x]=s[n-x+1,n]（根据定义可得），它们两个串的最后 l 个字符一定相等，可得 s[x-l+1,x]=s[n-l+1,n]。联立两个式子，得 s[1,l]=s[x-l+1,x]，即 l\in bd(x)。

于是我们只需要维护 fail 数组。由于上面性质中 bd(pre(fail(n))) 也可以用这个性质来化简：bd(pre(fail(n)))\subseteq{fail(fail(n))}\cup bd(pre(fail(fail(n))))。如此嵌套，可得 bd(s)\subseteq\{fail(n),fail(fail(n)),\cdots\}。

举例：s=\texttt{abababababaaabba}。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
string s;
int fail[N];
int main(){
    cin>>s;
    int n=s.size();
    s=" "+s;
    for(int i=1;i<=n;i++){
        for(int j=fail[i-1];j;j=fail[j])
            if(s[j+1]==s[i]){
                fail[i]=j+1;
                break;
            }
        if(fail[i]==0&&s[1]==s[i]&&i>1) fail[i]=1; 
    }
    for(int i=1;i<=n;i++) printf("%d ",fail[i]);
    return 0;
}

然而有一种更简单的写法，也就是市面上大多数的板子：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
string s;
int fail[N];
int main(){
    cin>>s;
    int n=s.size();
    for(int i=2,j=0;i<=n;i++){
        while(j!=0&&s[j]!=s[i-1]) j=fail[j];
        if(s[j]==s[i-1]) j++;
        fail[i]=j;
    }
    for(int i=1;i<=n;i++) printf("%d ",fail[i]);
    return 0;
}

模板

也就很简单了，将两个串拼接到一起，中间插入一个奇怪字符，如果某个位置的 fail 值恰好等于要查找的串的长度，那么就找到了。模板。

例题

包括但不限于：

由于我太菜了，故不能对每道题分别写题解。

一些其他用法

处理循环节

另 pd(s) 为 s 的所有周期的长度集合，即 pd(s)={x|\forall 1\le i\le n-x+1,s[i,i+x-1]=s[i+x,i+2x-1]}，则有性质 pd(s)+bd(s)=n，换句话说如果 l\in bd(s) 则 n-l \in pd(s)。易证。所以看到循环时可以思考能否转换为 bd 的相关问题。

失配树

将 i\to fail(i) 建立一条边，构成一棵树。由上文的性质：

所以所有的 bd(i) 都是从 i 不断跳 bd 找到的，故都在点 i 到根了路径（根链）上。