Introduction to KMP

Background

在字符串理论中，经常要求一个字符串$T$在另一个字符串$S$中所有出现的位置。这个过程就是字符串匹配。我们称$S$为文本，$T$为模式。下面介绍一种时间复杂度为线性的算法 KMP，可以解决此类问题。

Introduction

令$S_i$表示字符串$S$的第$i$个字符，$S_{i, j}$表示字符串$S$的第$i$到第$j$个字符构成的字符串。为了方便讲解，字符串下标从$1$开始。

在 KMP 中有一个重要的数组，我们称它为$nxt$。对于一个字符串$S$，$nxt_i=\max(x \mid x \lt i \land S_{1, x}=S_{i-x+1, i})$。特别的，令$nxt_1=0$。

考虑如何求出模式$T$的$nxt$数组。最暴力的暴力时间复杂度为$O(n^2)$，但这实际上浪费了很多有用的信息。其实可以从$nxt_{i-1}$推到$nxt_i$。

我们来形象化这个过程

    v
acbacabacbacb
           ^

假设我们已经求出$nxt_{12}=5, \ nxt_5=2$，当前两个指针分别指向$S_{12}$和$S_{nxt_{12}}=S_5$，求$nxt_{13}$。在这里，两个指向$S_p, S_q$的指针表示$S_{p-q+1, p}=S_{1, q}$。

比较两个指针的后一位。易知，若$S_{13}=S_6$，则$nxt_{13}=nxt_{12}+1=6$，可以将两个指针都向后移一位。

否则，我们已经知道$nxt_{12}=5$，即$S_{1, 5}=S_{8, 12}$，而$nxt_5=2$，即$S_{1, 2}=S_{4, 5}=S_{11, 12}$。这意味着我们可以把指向$S_{nxt_{12}}$的指针重新指向$S_{nxt_{nxt_{12}}}=S_2$，如下

 v
acbacbaacbacb
           ^

此时仍然满足$S_{12-2+1, 12}=S_{1, 2}$。再次比较两个指针的后一位，发现$S_{13}=S_3$，于是$nxt_{13}=nxt_{2}+1=3$，将两个指针向后移一位。当然，若$S_{13} \neq S_3$则需要将指向$S_{nxt_5}$的指针再指向$S_{nxt_{nxt_5}}$，重复上述过程，直到指针指向$S_0$，那么$nxt_{13}=0$。

代码并不复杂（该代码中的字符串下标从$0$开始）

void kmp(char c[], int len) {
  nxt[0] = -1;
  for (int i = 1; i < len; ++i) {
    for (nxt[i] = nxt[i - 1]; ~nxt[i] && c[nxt[i] + 1] != c[i];
         nxt[i] = nxt[nxt[i]])
      ;
    if (c[nxt[i] + 1] == c[i])
      ++nxt[i];
  }
}

在得到模式$T$的$nxt$数组后，我们就可以用类似的方法求出$T$在文本$S$中所有出现的位置了。思路也是维护两个指针，一个在$S$上，指向$S_p$，另一个在$T$上，指向$T_q$，同样要满足$S_{p-q+1, p}=T_{1, q}$。显然，当$q=|T|$时，就找到了一个出现的位置。

Application

KMP 算法除了可以用于字符串匹配，还能求出一个循环串的最小循环节。循环串是由至少两个相同的字符串拼接起来得到的字符串。

具体来讲，设$i=|S|$，$nxt_i \gt 0 \land i-nxt_i \mid i \Rightarrow S_{1, i}$是循环串，它的最小循环节是$S_{1, i-nxt_i}$。

要证明以上结论，只需要证明：

• 引理 1 所有非循环串均不满足上述条件。

证明 显然，在满足上述条件的情况下，$S$的确是循环串，$S_{1, i-nxt_i}$就是$S$的一个循环节。

• 引理 2 对于两个字符串$A, B$，若$AB=BA$，则$AB$是循环串，$A_{1, (|A|, |B|)}=B_{1, (|A|, |B|)}$是一个循环节。其中$(a, b)$表示$a, b$的最大公约数。

证明 设$|A| \le |B|$，由$AB=BA$可知，$A=B_{1, |A|}=B_{|A|+1, 2|A|}=\cdots$，那么当$(|A|) \mid (|B|)$时，$A$是$B$的一个循环节（或$A=B$），因此$AB$是循环串。

当$(|A|) \nmid (|B|)$时，令$k=\left\lfloor {|B| \over |A|} \right\rfloor$。

考虑字符串$S=AB, \ T=S_{(k-1)|A|+1, |S|}$，可知$T_{1, |A|}=T_{|T|-|A|+1, |T|}=A, \ T_{1, |T|-|A|}=T_{|A|+1, |T|}=B_{(k-1)|A|+1, |B|}$。令$A’=B_{(k-1)|A|+1, |B|}, \ B’=A$，那么我们又得到了$A’B’=B’A’$的形式，此时$|A’|=|B| \bmod |A|, \ |B’|=|A|$。因此，最后一定能得到长为$(|A|, |B|)$的字符串，它是$A, B$的一个循环节，也是$AB$的一个循环节。

• 引理 3 若字符串$S$是循环串，则$S$的最小循环节是$S_{1, i-nxt_i}$。

证明 令$x$为最小循环节的长度，只要证明不存在$y$满足$y \lt x$且$S_{1, i-y}=S_{y+1, i}$。

假设存在这样的$y$，那么$S_{y+1, y+x}=S_{1, x}=S_{x+1, 2x}$。令$A=S_{y+1, x}, \ B=S_{x+1, y+x}$，可以发现$A$是$S_{1, x}$的后缀、$S_{y+1, y+x}$的前缀，$B$是$S_{x+1, 2x}$的前缀、$S_{y+1, y+x}$的后缀，即$S_{1, x}=AB=BA$，根据引理 2，$S_{1, x}$是循环串，这与$x$是最小循环节的长度矛盾。因此这样的$y$不存在，而因为$S_{1, x}$是一个循环节，所以$S_{1, i-x}=S_{x+1, i}$，根据 KMP 的原理，$nxt_i=i-x$，即$S$的最小循环节是$S_{1, i-nxt_i}$。

由此命题得证。