KMP 字符串匹配

字符串匹配问题指对于字符串 SS 与 TT，判断 TT 是否为 SS 的子串，并在 SS 中找到 TT 所有出现的位置。KMP 算法能在优秀的时间复杂度内解决该问题。

前缀函数

对于字符串 SS，前缀函数 nxtinxt_i 定义为 SS 中以 ii 结尾的非前缀子串 与 SS 的前缀能够匹配的最长长度。即 nxti=max⁡{j}nxt_i=\max\{j\} 满足 j<ij<i 且 S[1,j]=S[i−j+1,i]S_{[1,j]}=S_{[i-j+1,i]}。特别的，若不存在这样的 jj，则 nxti=0nxt_i=0。

接下来的文章中，我们称对于一个位置 ii，nxtinxt_i 的“候选项”为所有满足 j<ij<i 且 S[1,j]=S[i−j+1,i]S_{[1,j]}=S_{[i-j+1,i]} 的 jj。

考虑如何计算前缀函数，朴素计算是 O(n3)O(n^3) 的。但是前缀函数有如下性质：

  • nxti+1nxt_{i+1} 最多比 nxtinxt_i 大 11。较为显然，证明略。

  • 若 j0j_0 是 nxtinxt_i 的一个候选项，那么小于 j0j_0 的所有 nxtinxt_i 的候选项中，最大的候选项是 nxtj0nxt_{j_0}。证明可以考虑反正，假设存在 j1j_1 满足 nxtj0<j1<j0nxt_{j_0}<j_1<j_0，那么根据定义，有 S[1,j0]=S[i−j0+1,i]S_{[1,j_0]}=S_{[i-j_0+1,i]} 与 S[1,j1]=S[i−j1+1,i]S_{[1,j_1]}=S_{[i-j_1+1,i]}。那么 S[j0−j1+1,j0]=S[i−j1+1,i]=S[1,j1]S_{[j_0-j_1+1,j_0]}=S_{[i-j_1+1,i]}=S_{[1,j_1]}，所以 j1j_1 是 nxtj0nxt_{j_0} 的候选项，与 j1>nxtj0j_1>nxt_{j_0} 矛盾。

有了如上性质，我们就可以再处理每一位时，暴力跳上一位的 nxtnxt，判断下一位是否与这一位相同即可。代码实现较易，如下：

nxt[1]=0;
rep(i,2,m){
  int j=nxt[i-1];
  while(j&&t[i]!=t[j+1]) j=nxt[j];
  if(t[i]==t[j+1]) j++;
  nxt[i]=j;
}

复杂度：观察 jj 的变化，每次 jj 最多 +1+1，且 jj 非负，jj 减小幅度不超过 jj 的增加幅度，故 jj 最多变化 2n2n 次，故复杂度 O(n)O(n)。

KMP 算法

与前缀函数类似，令 fif_i 表示 TT 中以 ii 结尾的子串与 SS 的前缀能够匹配的最长长度。求解方法也类似。代码如下：

rep(i,1,n){
  int j=f[i-1];
  while(j&&s[i]!=t[j+1]) j=nxt[j];
  if(s[i]==t[j+1]) j++;
  f[i]=j;
}

exKMP（Z 函数）

回想一下，KMP 算法求解的是字符串中以每一个位置结尾的最长的与字符串前缀匹配的子串。而 exKMP 则是求解字符串中以每一位为开头的后缀与字符串的 LCP，即最长公共前缀。我们称 以 ii 位置开头的后缀与字符串前缀的 LCP 长度为 ZiZ_i。

假设字符串下标从 00 开始，则对于 Z 函数，有如下性质：对于 i>0i>0，对于任意的 0≤l<i0\le l<i 都有：

∀0≤x≤min⁡(Zi−l,l+Zl−i),Si+x=Sx\forall 0\le x\le\min(Z_{i-l},l+Z_l-i),S_{i+x}=S_{x}

证明：

Si+x=Sl+i−l+x=Si−l+x(x≤l+Zl−i)=S(i−l)+x=Sx(x≤Zi−l)\begin{aligned} S_{i+x}=&S_{l+i-l+x}\\ =&S_{i-l+x}(x\le l+Z_l-i)\\ =&S_{(i-l)+x}\\ =&S_x(x\le Z_{i-l}) \end{aligned}

故对于每一位 ii，初始化 Zi=min⁡(Zi−l,l+Zl−i)Z_i=\min(Z_{i-l},l+Z_l-i)，暴力向后匹配即可。当取 ll 为 i+Zii+Z_i 最大的 ii 时，每个字符只会被暴力判断一次，故复杂度为 O(n)O(n)。代码如下，±1\pm 1 的细节较多。

int l=0; z[0]=SZ(s);
rep(i,1,SZ(s)-1){
  z[i]=max(0ll,min(z[i-l],l+z[l]-i));
  while(i+z[i]<SZ(s)&&s[z[i]]==s[i+z[i]]) z[i]++;
  if(i+z[i]>l+z[l]) l=i;
}