1   Prologue

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

2   Notations

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

模式串、文本串

所谓 模式串 ，是指你想要找到（或者得到位置 &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 开始 —— 甚至包括费波拉契数列也如此。

3   Main Idea

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

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

4   MP 算法

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

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;
}

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

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;
    }
}

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;
}

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;
    }
}

5   KMP 算法

其实 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 数组：

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

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 数组如下，请您欣赏：

6   复杂度分析

至于为什么 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 的情况了）。

所以就是线性的了！

7   KMP 算法的最长停顿

为了说明 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 数组如下，我们一会儿要用到，你也可以先把它当作找规律的题看看：

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

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 便是文本串上的一个字符的最多比较次数。

8   为什么费波拉契串这么神奇

为了证明为何费波拉契串就是使停顿时间最长的模式串，我们再看看 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 算法的停顿时间达到最长的极限情况——很容易发现，满足这条件的便是费波拉契串了。

9   PS

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

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

10   References

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