这是什么模式匹配算法？

Question

我正在读的理论&数据结构的问题（西摩Lipschuz）。

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

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

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

或者，这是作者生产的任何新算法？

Answer 1

我相信这是KMP算法。 KMP构造了一个“失败表”，它本质上是一个自动机，说“如果你对特定字符不匹配，你还能匹配多少模式字符串？”它也对模式进行预处理，而不是匹配的字符串。此外，如果您看一下Aho-Corasick算法（这是KMP的泛化），则会构建此自动机的更通用版本，该版本可以一次处理多个模式。因此，我非常肯定你在看KMP。