这是什么模式匹配算法？

Question

我正在读一本书“数据结构的理论与问题”(Seymour Lipschuz)。

让我提供我正在阅读的部分的图像。

。

本书的这一部分讨论了一种名为“第二模式匹配算法”的模式匹配算法。

这是什么算法？这是Boyer-Moore还是KMP或者Horspool还是什么？

或者，这是作者提出的新算法吗？

Answer 1

我相信这就是KMP算法。KMP构建了一个“故障表”，它本质上是一个自动机，它说“如果你在一个特定的字符上不匹配，那么你还能匹配多少模式字符串？”它还对模式进行预处理，而不是对要匹配的字符串进行预处理。此外，如果你看看Aho-Corasick算法，它是KMP的推广，它构建了一个更通用的自动机版本，可以同时处理多个模式。因此，我非常确定您正在查看KMP。