定义

约定记号

$s[l,r]$ 代表从 $l$ 到 $r$ 的子串。

$\pi$ 函数

对于一个字符串 $s$，它的 $\pi$ 函数是它的前缀和后缀相等的最长长度。

$$ \pi=\max_{s[1,i]=s[n-i+1,n]} i $$

进一步，我们定义 $\pi_i$ 是字符串前 $i$ 个字符组成的子串的 $\pi$ 函数值。特别的，定义 $\pi_1 =0$。

下面我们考虑如何求出 $\pi$ 数组。

对于 $\pi_1=0$ 是确定的，考虑递推。

假设我们当前求出了 $\pi_1,\pi_2,\cdots,\pi_i$ 要求出 $\pi_{i+1}$。

有一个特殊情况，如果 $s[\pi_i+1]=s[i+1]$，那么 $pi_{i+1}=\pi_i+1$。

根据 $\pi$ 函数定义，$s[1,\pi_i]=s[i-\pi_i+1,i]$，那么如果 $s[\pi_i+1]=s[i+1]$，就有了 $s[1,\pi_i+1]=s[i-\pi_i+1,i+1]$，进而有 $\pi_{i+1}=\pi_i+1$。

下面考虑当 $s[i+1]\ne s[\pi_i+1]$ 时的情况：

还是一样的，$s[1,\pi_i]=s[i-\pi_i+1,i]$，$\pi_{i+1}$ 肯定不比 $\pi_i$ 大，所以我们要在 $[1,\pi_i]$ 中找到一个最大的 $j$ 使得 $s[i-j+1,i+1]=s[1,j+1]$，此时 $\pi_{i+1}=j+1$。

注意到此时 $s[1,j]$ 是 $s[1,\pi_i]$ 的前缀，$s[i-j+1,i]$ 是 $s[i-\pi_i+1,i]$ 的后缀，又因为 $s[1,\pi_i]=s[i-\pi_i+1,i]$，所以 $[i-j+1,i]$ 是 $s[1,\pi_i]$ 的后缀。

当满足 $s[i-j+1,i+1]=s[1,j+1]$ 且 $j$ 最大时，也就是 $s[1,\pi_i]$ 的前缀和后缀相等且长度最长的时候，我们发现此时正好和 $\pi$ 的定义对上了，那么此时的 $j$ 就是 $\pi_{\pi_i}$。

若此时 $s[j+1]=s[i+1]$，那么 $\pi_{i+1}=j+1$。否则一直这么找下去，直到真的没有相同的前后缀。

求 $\pi$ 数组代码：

1
2
3
4
5
6
7
pi[1]=0;
for(int i=2;i<=n;i++){
    int j=pi[i-1];
    while(j&&s[j+1]!=s[i])j=pi[j];
    if(s[i]==s[j+1])j++;
    pi[i]=j;
}

KMP 算法

该算法用于解决这样的问题：

给定文本串 $s$ 和模式串 $t$，求 $s$ 中所有出现的 $t$ 的位置。

我们可以使用这样的方法来解决：令 $f=s+c+t$，其中 $c$ 是不属于字符集的一个字符，求 $f$ 的 $\pi$ 数组，若 $\pi_i=len_t$，则在以 $i$ 为结尾的位置匹配上了。代码略。

另外还有一种不用显式建出字符串 $f$ 的方法：我们先跑出 $t$ 的 $\pi$ 数组，然后直接匹配，过程类似于求 $\pi$ 数组，具体见代码，其中 $mth_i$ 表示到 $s_i$ 匹配了多少位。

1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=n;i++){
    int j=mth[i-1];
    while(j&&t[j+1]!=s[i])j=pi[j];
    if(t[j+1]==s[i])j++;
    mth[i]=j;
    if(j==m){
        // 此时匹配上了
        j=pi[j];
    }
}