[Algorithm] 字符串匹配： MP，KMP，暴力搜索等(ZT)

MP/KMP 算法详解

By

Contents

本篇文章主要针对的是对字符串匹配有兴趣的生物以及被某版本数据结构与算法教材中的 KMP 算法讲解弄得不知所云但与此同时却还难能可贵地保持着旺盛求知欲的不幸生在了错误年代的可怜童鞋，其他生物阅读本文前请慎重考虑因为它 可能对您的大脑（如果有）、小脑甚至包括脊髓都造成严重且不可恢复的创伤 。

下文可能会提到 “模式串”、“文本串”、“窗口” 这些词，它们的定义如下，如果这些文字使你头晕，请及时做好救治准备。

模式串、文本串

所谓 模式串 ，是指你想要找到（或者得到位置 &etc.）的字符串；而 文本串 ，则是指搜索的目标字符串。

比如说你要在 "lucky dog" 中寻找 "dog" ，那么 "dog" 是模式串， "lucky dog" 则是文本串；

而你若要在 "If is a lucky dog" 中寻找 "lucky dog" ，那么 "lucky dog" 便成了模式串， "If is a lucky dog" 则是文本串。

Understand?

窗口

无论用什么样的搜索算法，在搜索的过程中，总是需要将模式串与文本串进行比较，它们对齐的那部分区域，也就是们关心的那块区域，咱称为 窗口 。

另外，为了避免让已经适应 C/C++/C#/D/Java/JavaScript/Python/Go/... 语言思维的童鞋多绕一个弯，本文用到的数组下标都以 0 开始 —— 甚至包括费波拉契数列也如此。

MP/KMP 字符串搜索算法的思想精华在于利用已经匹配的部分包含的信息，加速搜索的过程。

嗯——已经匹配的部分包含什么信息？

它已经匹配了！

举例说，在某个字符串中查找子串 A B C D A B D A C 时，如果遇到 A B C D A B ，而紧跟其后的不是 D ，这时候我们可以将窗口右移四位（而不是一位），因为既然 A B C D A B 已经匹配了， 那么移动当前窗口之后 已经匹配过的地方 肯定需要保证 依然匹配 ，这里最好的做法即让 A B 相互对齐:

. . A B C D A B ? . . . . . .
    A B C D A B D A C

=>

. . A B C D A B ? . . . . . .
            A B C D A B D A C

因为，看呀，如果只右移一位，那么:

. . . . . . . . . . . . . . . // 先不用管这个字符串
    A B C D A B . . .         // 已经匹配的部分
=>    A B C D A B D A C
      |
    糟糕！

如上面所示， A B C D A B 匹配了，那么移动一位之后，第一个字符 A 就肯定会对着 B ，绝对不可能在这个地方找到匹配

右移两位、三位或者四位时发生的状况可以依此类推；而右移四位时就不同了:

. . . . . . . . . . . . . . . // 暂时还不用管这个字符串
    A B C D A B . . .         // 已经匹配的部分
=>          A B C D A B D A C

这个时候才 可能 成功匹配。

MP 算法基于这样一种观察：

Note

注意了，这里以及下面所说的 前缀 和 后缀 都是指 不包括自身 的“真”前缀或后缀 ( proper prefix/suffix )

发生了不匹配之后，移动窗口时，定要保证 将模式串已匹配部分的一个前缀和一个相同的后缀对齐，并使这个前缀尽可能长 。

什么意思？

首先让我们列出模式串 A B C D A B 的所有前缀：

0: /*Empty*/
1: A
2: A B
3: A B C
4: A B C D
5: A B C D A

我们再列出它所有的后缀：

0: /*Empty*/
1: B
2: A B
3: D A B
4: C D A B
5: B C D A B

发现前缀 A B == 后缀 A B ，将它们对齐（即，接下来直接从第 3 位开始比较），完美了，前两位不必重复比较了。

原理上说也不难理解： 从左向右移动窗口的过程就是用前缀去匹配后缀的过程 ，而第一次匹配成功的肯定是最长的相同前缀/后缀 —— 在上例中，两个空字串也相等，可是如果将它们对齐的话那可就“移过头了”。

这么看，我们发现，在模式串的每一个位置上，匹配失败之后能最大限度的将窗口移动多少位 —— 即，与什么位置对齐， 只与模式串在该位置前方的子串有关 ，与文本串无关，与模式串在该点之后的字符也无关。

于是，自然而然的就想到了，为什么不把这么个失败后对齐的位置存放在一个数组中呢，这样每次匹配失败之后就按照它的指示进行跳转。

令 F[i] == max{ j | pattern[0:j) == pattern[i-j+1:i+1) and 0 ，也就是当前位置上保证前缀等于后缀的最大长度。

对于模式串 A B C D A B D A C , F 数组如下：

Index	0	1	2	3	4	5	6	7	8
Pattern	A	B	C	D	A	B	D	A	C
F	0	0	0	0	1	2	0	1	0

继续扯，在位置 i 匹配失败之后，可以将窗口继续右移一位，并从 F[i-1] 位置开始继续比较模式串与文本串（按照定义，pattern[ 0 : F[i-1] ) 已经保证匹配了），用代码表示的话就是这样：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m];
    calcF (pattern, F); // 计算跳转数组
    for(;text[i];++i,++j) {
        while(j>=0 && pattern[j]!=text[i]) {
            // 第一个字符不匹配则右移窗口、从 0 开始比较
            if (j==0) {
                j=-1;
                break;
            }
            j = F[j-1]; // 对齐
        }
        if(j>=m-1) {    // 找到了！
            return (i+1-m);
        }
    }
    return -1;
}

—— 多和谐呀！

对了，内个 F 数组怎么算？

观察一下，希望求出拥有相同后缀的最长前缀，这个过程不也是一个字符串匹配的过程吗：

1.  A B C D A B D A C
    A B C D A B D A C
    |
    0  // 定义为 0

2.    A B C D A B D A C
    A B C D A B D A C
      |
      0 // 匹配部分的长度

3.      A B C D A B D A C
    A B C D A B D A C
        |
        0

4.        A B C D A B D A C
    A B C D A B D A C
          |
          0

5.6.        A B C D A B D A C
    A B C D A B D A C
            | |
            1 2

7.              A B C D A B D A C
    A B C D A B D A C
                |
                0

8.                A B C D A B D A C
    A B C D A B D A C
                  |
                  1

9.                  A B C D A B D A C
    A B C D A B D A C
                    |
                    0

如上面所示，将模式串向右移动，并与自身做比较，在位置 i 上，pattern[i:] 与 pattern 自身相匹配的部分的长度就是 F[i] 。

注意第6步到第7步！ 为什么可以直接右移两位呢？

—— 因为 F[1] 已经算出来了！于是我们可以将之前 MP 算法中的思想用在这里，聪明的你想到了没有？

用代码来说就是这样的，看不懂的话我会很伤心：

void calcF(char const* pattern, int* F)
{
    int i=0,j=0;
    for(;pattern[i];++i,++j) {
        while(j>0 && pattern[j-1]!=pattern[i]) {
            j = F[j-1];
        }
        F[i] = j;
    }
}

对了有没有人觉得 MP 算法中对于第一个字符不匹配时的特殊处理感觉到很生硬的？

嗯，其实呢，考虑到第一个字符失败时的特殊情况其实也不怎么特殊，不如干脆把这种情况也放到 F 数组中去统一处理好了：

Index	0	1	2	3	4	5	6	7	8	9
Pattern	A	B	C	D	A	B	D	A	C
F	-1	0	0	0	0	1	2	0	1	0

这样，MP 算法表达起来更简单了：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F); // 计算跳转数组
    for(;text[i];++i,++j) {
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];   // 对齐
        }
        if(j>=m-1) {    // 找到了！
            return (i+1-m);
        }
    }
    return -1;
}

calcF 也并没有因此变复杂：

void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        F[i+1] = j+1;
    }
}

理解之后就会觉得，这种表示方法比较 “省事”；下面咱就都用这种表示得了。

Nevertheless, 其实它们是一码事。

我们再停下来看看 “暴力” 搜索算法 —— 有没有可能暴力算法比 MP 算法还快呢？

答案是 “Yes!”

( 哈哈！你输了吧！ )

让我们想象一下在一个字符集很大的串 —— 比如说 UTF-16 字符串吧，中寻找一段模式串；而模式串的第一个字符出现在文本串中的频率根本就不大，那么看看第一次匹配失败时它们两者工作的流程吧：

MP 算法	暴力算法
i>=n? j>=0? ( 此时 j == 0 ) 比较 pattern[j] 与 text[i] j = F[j] j>=0? ( 此时 j == -1 ) j = j+1 j >= m? i = i+1 到第 1 步	i>=n? j = 0 j < m? 比较 pattern[j] 与 text[i] i = i+1 到第 1 步

嗯，所以说，这个地方是有优化空间的，Knuth、Morris、Pratt 的论文 中有提到，俺就不展开了 —— 因为真正牛B的优化在下面：

其实 MP 算法的效率还有提升的空间，不过从模式串 A B C D A B D A C 中看不明显；我们试试这样一个模式串： A B A B A B C 。

假设在 A B C A B C A B A B A B C A C 中查找 A B A B A B C ，按照 MP 算法的思想，先算出 F 数组：

Pattern	A	B	A	B	A	B	C
F	-1	0	0	1	2	3	4	0

于是查找的过程就是这样的：

1.  A B C A B C A B A B A B C A C
    A B A . . . .

2.  A B C A B C A B A B A B C A C
        A . . . . . .

3.  A B C A B C A B A B A B C A C
          A B A . . . .

4.  A B C A B C A B A B A B C A C
              A . . . . . .

5.  A B C A B C A B A B A B C A C
                A B A B A B C

从第 1 步到第 2 步、从第 3 步到第 4 步，我们发现，字符 A 与 C 的不匹配导致了第一次失败，然后紧接着又直接导致了第二次失败。

如此，我们又惊喜的发现，在 A B 之后若是遇到不是 A 的字符，我们完全可以跳三步！因为跳两步的话算是把 A 对齐了 —— 可是它们会被对齐到一个不是 A 的、将会导致匹配失败的字符上面去。

这样的规则有什么规律呢？我直接放出代码吧：

// 这是我们计算 MP 算法中的 F 数组的函数：
void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        F[i+1] = j+1;
    }
}

睁大眼睛准备找茬喽：

// 只需要改一句话：
void calcF(char const* pattern, int* F)
{
    int i=0,j=-1;
    F[0]=-1;
    for(;pattern[i];++i,++j) {
        while(j>=0 && pattern[j]!=pattern[i]) {
            j = F[j];
        }
        // !这里!
        F[i+1] = pattern[j+1] == pattern[i+1]?
                   F[j+1]:
                   j+1;
    }
}

为什么呢？因为对于同一个字符导致的失败，失败在前面应该跳到哪里，到后面就还是应该跳到哪里。

另外，这个时候咱似乎就比较喜欢把这个数组称作 next 数组了 —— 其实还是同一回事。

那么， A B A B A B C 的 next 数组如下，请您欣赏：

Index	0	1	2	3	4	5	6
Pattern	A	B	A	B	A	B	C
Next	-1	0	-1	0	-1	0	4	0

至于为什么 KMP 算法的复杂度是线性的，我们再回头看看 一节中的算法主体：

int MP(char const* pattern, char const* text)
{
    int i=0,j=0,m=strlen(pattern);
    int F[m+1];
    calcF (pattern, F);
    for(;text[i];++i,++j) { // j 增大，i 增大
        while(j>=0 && pattern[j]!=text[i]) {
            j = F[j];       // j 减小
        }
        if(j>=m-1) {
            return (i+1-m);
        }
    }
    return -1;
}

i 只有增大的份，所以 ++i 最多执行 n 次，这个很显然。

j 初始值为 0，一共增加了 n 次，而 j>=-1 ，于是 j = F[j] 这一句最多也就执行了 n+1 次（否则就会出现 j<-1 的情况了）。

所以就是线性的了！

为了说明 KMP 算法在文本串上的某一个字符上进行了很多次比较的极限情况（也就是所谓的停顿或者E文的 delay ），我们首先要介绍一下 “费波拉契串” —— 因为，很巧，它就是能使 KMP 算法达到最糟糕状况的模式串，一会儿我们会说到。

提到 “费波拉契” ，相信不少人会直接想到 1, 1, 2, 3, 5, 8, 13, 21, 34 ... ，是的，费波拉契串的定义也十分类似：

设 P 是个费波拉契串，那么：

P[0] = b
P[1] = a
P[i] = P[i-1]P[i-2]

所以：

P[2] = ab
P[3] = aba
P[4] = abaab
P[5] = abaababa
P[6] = abaababaabaab
P[7] = abaababaabaababaababa
P[8] = abaababaabaababaababaabaababaabaab
...

计算出 P[7] 的 F 数组和 Next 数组如下，我们一会儿要用到，你也可以先把它当作找规律的题看看：

P	a	b	a	a	b	a	b	a	a	b	a	a	b	a	b	a	a	b	a	b	a
n	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21
F	-1	0	0	1	1	2	3	2	3	4	5	6	4	5	6	7	8	9	10	11	7	8
Next	-1	0	-1	1	0	-1	3	-1	1	0	-1	6	0	-1	3	-1	1	0	-1	11	-1	8

费波拉契串有几个性质值得注意一下：

Note

文章前面已经假设了我的世界里费波拉契数列下标是从 0 开始的，这里再强调一遍。

1. strlen(P[n]) == Fibonacci[n] （这个应该很容易理解吧）

2. 设函数 c(t) 的作用是交换字符串 t 的最后两个字符，例如 c("abcdef") == "abcdfe"，那么当 n>=2 时 P[n-1]P[n-2] == c(P[n-2]P[n-1]) ：

   n == 2 时这是显然的；

   当 n>2 时可以用数学归纳法证明：

   c(P[n-2]P[n-1]) = P[n-2]c(P[n-1]) = P[n-2]P[n-3]P[n-2] = P[n-1]P[n-2]
3. 由上面两条性质我们又可以推导出：

   Next[Fibonacci[n]-2] == F[Fibonacci[n]-2] == Fibonacci[n-1]-2, n>=2

   这是因为，可以把一个费波拉契串分解开：

   P[n] == P[n-1]P[n-2] == P[n-2]P[n-3]P[n-2] == c(P[n-3]P[n-2])P[n-2] == P[n-3]c(P[n-2])P[n-2] == ...

   具体以 P[7] 为例，

   P[7] == ab-ab-ba---ab------ba

   其中省略掉的部分根据 性质2 表现出的规律与前方相等，因此如果在 P[7] 的最后一个字符 b 处发生了不匹配，接下来应该在下列位置重新试着匹配：

   ab-a--b----a-------b-

   它们正好占据着 Fibonacci[2]-2, Fibonacci[3]-2, .. , Fibonacci[7]-2, ... 的位置。

因此，如果在费波拉契串的第 n 位，n == Fibonacci[k]-2 上发生了不匹配，接下来则还需要 k-1 次比较；

又因为 Fibonacci[k-1] == (φ^k - (-1)^kφ^-k)/sqrt(5) == round( φ^k / sqrt(5) )， 于是可以解得 k ~ log_φ(n)，其中 φ 是黄金比例 (1+sqrt(5))/2 == 1.618...

—— k 便是文本串上的一个字符的最多比较次数。

为了证明为何费波拉契串就是使停顿时间最长的模式串，我们再看看 MP 算法的基本思想：将字符串已匹配的一个前缀和一个对应的后缀匹配。

假设字符串 S 有且仅有一个相等的前缀和后缀（设为 a ），那么 S 可以表示为

S = aB = Ca

再假设 a 本身也有且仅有一个相等的前缀和后缀（设为 e ），那么 a 也可以表示为

a = eF = Ge

对应 MP 算法，匹配 Ca 时若在 a 之后失败，则会将 aB 的 a 与其对齐：

Cax
Cay

==>

Cax
 aBy

若在 B 的第一个字符处再次失败，则下一次对齐是这样的：

CGex
 GeBy

==>

CGex
  eFBy

KMP 算法在这里还要求 F 的第一个字符和 B 的第一个字符不等（否则会跳过这一段）

我们很容易可以证明想要 KMP 算法在这个地方停留尽可能长的时间需要满足 |S| <= |e| + |a| ：因为若 |e| + |a| > |S|，那么令 d = |e| + |a| - |S| 则 Ca = CGe = aB 算式中， a 和 e 将有长度为 d 的重叠，于是 B 的第一个字符等于 e[d]；同理，在 aB = eFB = Ca 算式中，可以得到 F 的第一个字符为 a[d]，由 a = eF 可以得到 a[d] = e[d]，和 KMP 的要求不符。

于是 |S| == |e| + |a| 是使 KMP 算法的停顿时间达到最长的极限情况——很容易发现，满足这条件的便是费波拉契串了。

对了，如果我要找出模式串在文本串中所有的出现怎么办？

提示一下：目前为止 F 数组（或者 next 数组）的最后一个元素我们还没有用到过是不是？

KNUTH D.E., MORRIS (Jr) J.H., PRATT V.R., 1977, Fast pattern matching in strings, SIAM Journal on Computing 6(1):323-350.

[2]

[3]

Last update: 2010/11/23 18:53:11