实现 Knuth-Morris-Pratt 算法

Knuth-Morris-Pratt（KMP）字符串匹配算法与我们刚刚实现的天真算法非常相似。基本区别在于，KMP 算法使用部分匹配的信息，并决定在任何不匹配的情况下停止匹配。它还可以预先计算模式可能存在的位置，从而减少重复比较或错误检查的次数。KMP 算法会预先计算一个表，这有助于搜索操作并提高效率。在执行 KMP 算法时，我们需要计算最长适当前缀后缀（LPS）。

让我们检查一下生成 LPS 部分的函数：

Unresolved include directive in modules/ROOT/pages/ch11/ch11-03.adoc - include::example$Chapter11/3.php[]

对于前面例子中的 AABA 模式，LPS 将是 [0,1,0,1]；现在，让我们为字符串/模式搜索问题编写 KMP 实现：

Unresolved include directive in modules/ROOT/pages/ch11/ch11-03.adoc - include::example$Chapter11/3.php[]

上述代码是 KMP 算法的实现。现在，让我们用我们实现的算法运行以下示例：

Unresolved include directive in modules/ROOT/pages/ch11/ch11-03.adoc - include::example$Chapter11/3.php[]

这将产生以下输出：

Pattern found at index : 0
Pattern found at index : 9
Pattern found at index : 16

KMP 算法的复杂度为 \$O(N+M)\$，远远优于常规模式匹配。其中，\$O (M)\$ 用于计算 LPS，\$O (N)\$ 用于 KMP 算法本身。

网上可以找到很多关于 KMP 算法的详细描述。