KMP 算法 —— 字符串匹配算法
字符串匹配
经常遇到的一个任务是在一段文字中定位一个词，类似地操作有，在一个字符串中定位一个子串的位置，这通常被称为字符串的模式匹配，以下简称字符串匹配。
那么，字符串匹配是什么？比如说，有一个字符串S="BBCD ABCDAB ABCDABCDABDAB"，其中是否包含另一个字符串T="ABCDABD"？如果有，子串T位于主串S中什么位置（可用T首字母在S中所在位置表示）。
本文主要介绍两种常用算法，朴素匹配算法和KMP算法及其改进版。KMP算法全称是Knuth–Morris–Pratt算法[1]，它以三个发明者命名 —— D.E.Knuth、J.H.Morris和V.R.Pratt。第一个K就是大名鼎鼎的图灵奖获得者Donald E. Knuth，他是广为流传的《计算机程序设计艺术》（TAOCP）系列的作者。不过，还有一个小八卦，他作为一名计算机科学家写自己著作的时候觉得当时世界上的排版系统太渣，于是暂放下写书工作，一举发明计算机排版系统TEX。总感觉像世外高人，冷不丁告诉世人他又练成了另一门绝世武功。我想现在很多用LaTex排版论文书籍的科技同仁们都知道他吧。
OK，言归正传，下面先介绍朴素匹配算法吧~
朴素匹配算法
索引定义
首先定义主串S和子串T的匹配索引i和j。
String S: | B | B | C | D | | A | B | C | D | ...
Index i: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | ...
String T: | A | B | C | D | A | B | D |
Index j: | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
算法原理
最直接也是最暴力的思路就是 —— 按顺序依次比较子串T中字符和主串S中字符。如果不一致就后移子串T，直至找出主串S中（所有）子串T，或子串T已移出主串S范围。
示例如下：
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
1 - 首先，比较子串T的第一个字符与主串S的第一个字符，发现匹配失败，所以子串T后移一位。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
2 - 发现仍匹配失败，所以子串T继续后移，直至子串T与主串S的第一个字符成功匹配。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
3 - 接着依次比较第二个字符，匹配成功，继续比较下一位字符。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
4 - 直至又有字符不匹配为止。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
5 - 此时最直接的做法自然是，将子串T整个后移一位，再依次逐个比较。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
这就是朴素匹配算法。虽然可行，但时间复杂度很高，因为要把搜索位置移到已经比较过的位置，重新比较一遍，即索引i的回溯。
在下面算法实现中可以清楚看到，索引i和索引j的回溯。索引j的回溯是不可避免的，因为要确认匹配子串T中的每一个字符。那么，问题来了。。。
Q：能不能尽量避免索引i的回溯呢？
A：请见KMP算法。
时间复杂度
- 最好的情况是开始就匹配成功，则时间复杂度为
O(1)。 - 次好的情况只要首字符匹配上就完全匹配成功，则时间复杂度为
O(n+m)。其中，n为主串S长度，m为子串T长度。 - 最坏的情况是最终没有可匹配的字符串：在主串
S每一个字符处都比较一遍子串T的每一个字符。此时，时间复杂度为O((n-m+1)*m)。
算法实现
/* 朴素的模式匹配法，参考[2] */
int Index(String S, String T, int pos)
{
int i = pos; /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
int j = 1; /* j用于子串T中当前位置下标值 */
while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
{
if (S[i] == T[j]) /* 两字母相等则继续 */
{
++i;
++j;
}
else /* 指针后退重新开始匹配 */
{
/* i，j的回溯 */
i = i-j+2; /* i退回到上次匹配首位的下一位 */
j = 1; /* j退回到子串T的首位 */
}
}
if (j > T[0])
return i-T[0];
else
return 0;
}
KMP算法
KMP算法原理
让我们回到之前仅有最后一位字符不匹配的情况：
S: BBCD ABCDAB ABCDABCDABDAB
||||||
T: ABCDABD
当与D不匹配时，事实上我们知道前面已经成功匹配上的六个字符是ABCDAB。KMP算法的核心想法是，设法利用已经成功匹配的信息，不要搜索位置移回已经比较过的位置，继续把它向后移。即控制索引i不回溯，仅回溯索引j，通过减少不必要的回溯来提高算法执行效率。
那么显然，索引j回溯的距离仅取决于子串T本身的模式 —— 字符串结构中的重复规律。我们将子串T各位置的j值变化定义为一个数组Next，其程度与子串T相同。
6 - 这里先给出子串T的Next数组结果，能结合下面实例看懂即可，后面再介绍其定义和推导。
String T: | A | B | C | D | A | B | D |
Index j: | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Next[j]: | 0 | 1 | 1 | 1 | 1 | 2 | 3 |
此处，上接步骤4结果如下：
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
7 - 发现与D不匹配时，查字符D对应的Next[7]=3，即令索引j回溯至3，亦是子串T[3]与当前索引i对应位置对齐。
// `-`表示子串`T`跳过的距离
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ----ABCDABD
此外，我们还发现，C与空格对齐还避免了它前两个字符的比较。因为子串T结构中的重复规律已知，已经被考虑到Next数组的设计中去了，详见下面Next数组的定义。
8 - 索引j更新后对应字符C与空格比较，不匹配，则查C对应的Next[3]=1，即令索引j回溯至1，亦是子串T[1]与当前索引i对应位置对齐。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
9 - 索引j更新后对应字符A与空格比较，不匹配，则查A对应的Next[1]=0，即令索引j回溯至0，亦是子串T在当前索引i对应位置后移一位。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
10 - 如此比较，得到ABCDAB六位匹配，第七位不匹配。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
11 - 同上，令子串T的索引j回溯至3，并对齐。
// `-`表示子串`T`跳过的距离
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ----ABCDABD
12 - 向后依次比较字符，完成匹配。
S: BBCD ABCDAB ABCDABCDABDAB
|
T: ABCDABD
由上述过程可见，索引i一直不曾减小，这正是KMP算法的核心优势 —— 避免不必要的回溯。而且KMP算法在移动子串T的时候，利用自身重复规律，减少了比较次数（步骤7）。
Next数组定义
Next数组的作用可以直观理解为：若是当前字符匹配不成功，则指示比较对象由当前字符T[j]变为更新字符T[Next[j]]。
这里给出Next数组的函数定义如下：
$$
Next[j]=\left{\begin{array}{ll}
0 & \text{当}j=1 \text{时},\
max{k|1<k<j, \text{ 且 } p_1...p_{k-1} = p_{j-k+1}...p_{j-1}} &
\text{当此集合不空时},\
1 & \text{其他情况}.
\end{array}\right.
$$
String T: | A | B | C | D | A | B | D |
Index j: | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
Next[j]: | 0 | 1 | 1 | 1 | 1 | 2 | 3 |
-
j=1时，Next[1]=0； -
j=2时，属于其他情况，Next[2]=1； -
j=3时，j由1到j-1的字符串只有AB，无相等子串，属于其他情况，Next[3]=1； - 同理，
Next[4]=Next[5]=1； -
j=6时，j由1到j-1的字符串为ABCDA，前缀A与后缀A相同，可由上面公式推得k=2； -
j=7时，j由1到j-1的字符串为ABCDAB，最大重复前后缀为AB，可推得k=3；
事实上，也正是通过对最大重复前后缀长度的计算，得到索引j回溯的位置，可以跳过已知成功匹配的信息。
Trick：若最大重复前后缀长度为
x，则k=x+1.
时间复杂度
- KMP算法整体时间复杂度为
O(n+m)。其中，n为主串S长度，m为子串T长度。-
get_next函数的时间复杂度为O(m)， -
while循环的时间复杂度为O(n)。
-
KMP算法实现
计算子串T的next数组：
/* 通过计算返回子串T的next数组，参考[2] */
void get_next(String T, int *next)
{
int i,j;
i=1;
j=0;
next[1]=0;
while (i<T[0]) /* 此处T[0]表示串T的长度 */
{
if(j==0 || T[i]== T[j]) /* T[i]表示后缀的单个字符，T[j]表示前缀的单个字符 */
{
++i;
++j;
next[i] = j;
}
else
j= next[j]; /* 若字符不相同，则j值回溯 */
}
}
KMP算法的实现函数：
/* 参考[2] */
/* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0。 */
/* T非空，1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos)
{
int i = pos; /* i用于主串S中当前位置下标值，若pos不为1，则从pos位置开始匹配 */
int j = 1; /* j用于子串T中当前位置下标值 */
int next[255]; /* 定义一next数组 */
get_next(T, next); /* 对串T作分析，得到next数组 */
while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时，循环继续 */
{
if (j==0 || S[i] == T[j]) /* 两字母相等则继续，与朴素算法增加了j=0判断 */
{
++i;
++j;
}
else /* 指针后退重新开始匹配 */
/* 仅有j的回溯 */
j = next[j];/* j退回合适的位置，i值不变 */
}
if (j > T[0])
return i-T[0];
else
return 0;
}
PS：如果想从《部分匹配表》（Partial Match Table）角度理解KMP算法，可以参考[4],[5].
