本文概述
Knuth-Morris和Pratt介绍了用于字符串匹配问题的线性时间算法。通过避免与先前与要匹配的模式“ p”的某个元素进行比较所涉及的“ S”元素进行比较, 可以实现O（n）的匹配时间。即, 永远不会发生字符串“ S”的回溯
KMP算法的组成部分
1.前缀功能（Π）：模式的前缀功能Π封装了有关模式如何与自身偏移匹配的知识。该信息可用于避免模式“ p”的无用移位。换句话说, 这可以避免回溯字符串“ S”。
2. KMP Matcher：使用字符串“ S”, 模式“ p”和前缀函数“Π”作为输入, 在“ S”中查找“ p”的出现并返回“ p”的移位次数, 之后出现的次数为找到了。
前缀功能（Π）
以下伪代码计算前缀函数Π：
COMPUTE- PREFIX- FUNCTION (P)
1. m ←length [P] //'p' pattern to be matched
2. Π [1] ← 0
3. k ← 0
4. for q ← 2 to m
5. do while k > 0 and P [k + 1] ≠ P [q]
6. do k ← Π [k]
7. If P [k + 1] = P [q]
8. then k← k + 1
9. Π [q] ← k
10. Return Π运行时间分析
在上述用于计算前缀函数的伪代码中, 从步骤4到步骤10的for循环运行’m’次。步骤1至步骤3需要固定的时间。因此, 计算前缀函数的运行时间为O（m）。
示例：为以下模式“ p”计算Π：
解：
Initially: m = length [p] = 7
Π [1] = 0
k = 0
迭代6次后, 前缀函数计算完成：
KMP赛事
KMP匹配器以模式“ p”（字符串“ S”和前缀函数“Π”作为输入）在S中找到p的匹配项。下面的伪代码计算KMP算法的匹配组件：
KMP-MATCHER (T, P)
1. n ← length [T]
2. m ← length [P]
3. Π← COMPUTE-PREFIX-FUNCTION (P)
4. q ← 0 // numbers of characters matched
5. for i ← 1 to n // scan S from left to right
6. do while q > 0 and P [q + 1] ≠ T [i]
7. do q ← Π [q] // next character does not match
8. If P [q + 1] = T [i]
9. then q ← q + 1 // next character matches
10. If q = m // is all of p matched?
11. then print "Pattern occurs with shift" i - m
12. q ← Π [q] // look for the next match运行时间分析
从第5步开始的for循环运行’n’次, 即与字符串’S’的长度一样长。由于步骤1到步骤4需要固定的时间, 因此循环的运行时间主要由该时间决定。因此, 匹配函数的运行时间为O（n）。
示例：给定字符串“ T”和模式“ P”, 如下所示：
让我们执行KMP算法来查找“ T”中是否出现“ P”。
对于前缀函数“ p” , ？是先前计算的, 如下所示：
解：
Initially: n = size of T = 15
m = size of P = 7
已经发现模式’P’在字符串’T’中很复杂。找到匹配项所发生的总移位数为i-m = 13-7 = 6个移位。
