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}$。

由此命题得证。

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *