KMP算法
以下笔记来自阅读：Knuth D E , Morris J H , Pratt V R . Fast Pattern Matching in Strings[J]. Siam Journal on Computing, 1977, 6(2):323-350.
文本编辑器软件经常需要在一串字符中查找以匹配特定的模式，这些模式也是一串字符，我们有时需要查找到所有匹配的位置，也有时候，仅仅需要获取第一个匹配位置。例如，c a t e n a r y 包含模式 t e n 。
最直接的查找方式是在文本的每一个位置开始查找，如果没有匹配，就放弃该次查找。但是这种方式可能非常低效，举个例子，比如我们需要查找 a a a a a a a a a a a a a a b 中出现的 a a a a a a a b。模式是 anb, 文本是 a2nb，我们将需要进行 (n+1)2 次比较。另外，这种传统处理方式在遍历输入字符串的时候需要回退，这将给我们频繁用到的缓存操作带来麻烦（想像从磁盘读取数据到内存缓存）。
本文将描述一种模式匹配算法，该算法可以在 O(m + n) 时间内，从长度为n的字符串中查找长度为m的模式字符串的所有出现位置，并且不需要回退输入文本。算法仅需要占用 O(m) 的额外内存空间，并且复杂度和文本使用的字符表大小无关。
我们首先来从一个低效但是容易理解的角度理解算法。
通俗理解
算法背后的想法从这个角度更会容易理解：想像我们将模式字符串放置在输入字符串之上，
并且按照某种方式向右滑动模式字符串。比如：从 b a b c b a b c a b c a a b
c a b c a b c a c a b c 中查找 a b c a b c a c a
b。首先，我们将模式字符串放到最左侧，准备匹配输入字符串的第一个字符：
1
2
3a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑
1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑
现在我们匹配了一个字符，因此我们的模式字符串保持不动，继续扫描。很快，我们发现了另一个不匹配的字符：
1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑
此时我们已经匹配了除第四个字符以外的前三个字符，所以我们知道，输入字符串的最后四个字符是
a b c x
(x≠a)。我们不需要记录之前扫描过的字符串，因为我们目前在模式字符串中的位置就提供了重建这些字符串的足够信息。在上述的例子中，无论
x 是什么字符，只要不是 a,
我们可以直接将模式字符串右移4位，因为一位、两位、三位的移动都不可能匹配字符串。
1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑
1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑1
2
3 a b c a b c a c a b
b a b c b a b c a b c a a b c a b c a b c a c a b c
↑1
2
3
4
5
6
7 j = 1 2 3 4 5 6 7 8 9 10
pattern[j] = a b c a b c a c a b
next[j] = 0 1 1 0 1 1 0 5 0 1
注意： next[j] = 0 代表将模式字符串直接滑过当前的输入字符
在每步的扫描过程中，我们要么移动输入文本的指针，要么移动模式字符串，两者都最多能移动 n 次；因此，在构建 next 表后，最多需要 2n 步。当然模式字符串并没有真正的移动，只需要维护好指针 j 即可。
算法实现
模式匹配的过程可以描述为如下形式：
1
2
3
4
5
6
7
8
9place pattern at left;
while pattern not fully matched
and text not exhausted do
begin
while pattern character differs from
current text character
do shift pattern appropriately;
advance to next character of text;
end;1
2
3
4
5
6
7j := k := 1;
while j ≦ m and k ≦ n do
begin
while j > 0 and text[k] ≠ pattern[j]
do j := next[j];
k := k + 1; j := j + 1;
end;
为了严格证明上述程序的正确性，使用如下不变关系（invariant relation）：Let p = k - j (恰好位于和模式字符串对齐的前一个文本字符)，我们有 text[p + i] = pattern[i] for 1 ≦ i < j (当j > 0时，我们已经匹配了前面的j - 1个字符); 但是对于 0 ≦ t < p 有 text[t + i] ≠ pattern[i] for some i, 1 ≦ i ≦ m（在 p 之前不可能有对模式的完全匹配）。
程序要想正确是建立在能够计算 next
表之上的，只有这样，我们才能在做了 j := next[j]
的变换之后，依然保持上面的关系成立。现在，让我们看看如何计算
next 表。当程序设置 j := next[j]，我们知道 j >
0， 输入文本包含 text[k] 的最后 j 个字符是：
1
pattern[1] ... pattern[j - 1] x , x ≠ pattern[j]
1
pattern[1] ... pattern[i] x , pattern[i] ≠ pattern[j]
现在让我们来解决一直推迟的一个问题，如何计算 next[j]。
如果在定义 next[j] 时我们不要求 pattern[i] ≠
pattern[j]，这个问题将变得简单一些，因此我们先优先考虑这个简化的场景。
让 f[i] 代表满足如下条件的最大的 i (i < j):
1
pattern[1]...pattern[i - 1] = pattern[j - i + 1]..pattern[j - 1]
1
2
3 j = 1 2 3 4 5 6 7 8 9 10
pattern[j] = a b c a b c a c a b
f[j] = 0 1 1 1 2 3 4 5 1 21
2
3
4t := f[j];
while t > 0 and patter[j] ≠ pattern[t]
do t := next[t];
f[j + 1] := t + 1;1
2
3 a b c a b c a c a b
a b c a b c a c a b
↑1
2
3 a b c a b c a c a b
a b c a b c a c a b
↑
当我们知道如何计算 f[j]，离计算 next[j] 也就一步之遥了。对比两者的定义我们可以得到，对于 j > 1:
\[ next[j]= \begin{equation*} \left\{ \begin{aligned} f[j],\qquad&if pattern[j] ≠ pattern[f[j]] \\ next[f[j]],\qquad&if pattern[j] = pattern[f[j]] \end{aligned} \right. \end{equation*} \]
因此我们可以用如下的算法计算 next 表，其中也不需要存储
f[j]: 1
2
3
4
5
6
7
8
9
10j := 1; t := 0; next[1] := 0;
while j < m do
begin comment t = f[j]
while t > 0 and pattern[j] != pattern[t]
do t := next[t]
t := t + 1; j := j + 1;
if pattern[j] = pattern[t]
then next[j] := next[t];
else next[j] := t;
end
来总结一下，文本字符串可以使用两种思想来实现高效搜索：我们可以提前计算好需要的右移步数，这样当第 j 位发生不匹配时，我们可以按照计算结果进行移动；另外，对右移步数的计算是很高效的，同样可以应用模式匹配算法的思想：右移模式匹配字符串自己。