regmsif/hexo-blog @ e926dfe004c7b18baf462c23b8b8a2b1e7a2bc83

title: Introduction to KMP tags:

Knuth-Morris-Pratt Algorithm
Note id: "2524" categories:
- OI
- String date: 2018-03-14 14:25:20 ---

Background

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

Introduction

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

在 KMP 中有一个重要的数组，我们称它为$nxt$。对于一个字符串$S$，$nxti=\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, \ nxt5=2$，当前两个指针分别指向$S{12}$和$S{nxt{12}}=S5$，求$nxt{13}$。在这里，两个指向$S_p, Sq$的指针表示$S{p-q+1, p}=S_{1, q}$。

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

否则，我们已经知道$nxt{12}=5$，即$S{1, 5}=S_{8, 12}$，而$nxt5=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}=S3$，于是$nxt{13}=nxt{2}+1=3$，将两个指针向后移一位。当然，若$S{13} \neq S3$则需要将指向$S{nxt5}$的指针再指向$S{nxt_{nxt_5}}$，重复上述过程，直到指针指向$S0$，那么$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$上，指向$Tq$，同样要满足$S{p-q+1, p}=T_{1, q}$。显然，当$q=|T|$时，就找到了一个出现的位置。

Application

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

具体来讲，设$i=|S|$，$nxt_i \gt 0 \land i-nxti \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 的原理，$nxti=i-x$，即$S$的最小循环节是$S{1, i-nxt_i}$。

由此命题得证。

introduction-to-kmp.md 4.7 KB Riwayat Mentahan

Background

Introduction

Application

introduction-to-kmp.md 4.7 KB

Riwayat Mentahan