MP/KMP 算法详解 [草稿]
MP/KMP 算法详解
By If
Contents
1 Prelog
本篇文章主要针对的是对字符串匹配有兴趣的生物以及被某版本数据结构与算法教材中的 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?
- 窗口
- 无论用什么样的搜索算法，在搜索的过程中，总是需要将模式串与文本串进行比较，它们对齐的那部分区域，也就是们关心的那块区域，咱称为 窗口 。
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 算法
4.1 原理
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<j<i } ，也就是当前位置上保证前缀等于后缀的最大长度。
对于模式串 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 数组怎么算？
4.2 跳转数组的计算
观察一下，希望求出拥有相同后缀的最长前缀，这个过程不也是一个字符串匹配的过程吗：
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;
}
}
4.3 另一种表示
对了有没有人觉得 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, 其实它们是一码事。
4.4 可是...
我们再停下来看看 “暴力” 搜索算法 —— 有没有可能暴力算法比 MP 算法还快呢？
答案是 “Yes!”
( 哈哈！你输了吧！ )
让我们想象一下在一个字符集很大的串 —— 比如说 UTF-16 字符串吧，中寻找一段模式串；而模式串的第一个字符出现在文本串中的频率根本就不大，那么看看第一次匹配失败时它们两者工作的流程吧：
| MP 算法 | 暴力算法 |
|
|
嗯，所以说，这个地方是有优化空间的，Knuth、Morris、Pratt 的论文 [1] 中有提到，俺就不展开了 —— 因为真正牛B的优化在下面：
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 数组：
| 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 |
7 References
| [1] | 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] | http://www-igm.univ-mlv.fr/~lecroq/string/node8.html#SECTION0080 |
| [3] | http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching |
