这是什么模式匹配算法？

Question

这是什么模式匹配算法？

stringalgorithmpattern-matching

4

我正在阅读《数据结构的理论与问题》（Seymour Lipschuz）这本书。

让我提供一张我正在阅读的章节的图片： link of this book

。

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

这是什么算法？是Boyer-Moore、KMP、Horspool还是其他算法？

或者，这是作者创造的新算法吗？

- user366312

3

没有书的情况下，我们应该如何回答这个问题？ - Dan Grossman

1

好的，我们知道书的标题，但这如何帮助识别书中的算法呢？你认为所有程序员都有一本副本吗？ - Dan Grossman

我已经点击了链接，只是书的封面和购买链接。这里有一张截图。 - Dan Grossman

我认为谷歌已经在你的国家屏蔽了这本书。这本书托管在GoogleBooks上。 - user366312

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

我认为这是KMP算法。KMP构建了一个“失败表”，本质上是一个自动机，它说“如果您在特定字符上失配，您仍然可以匹配多少模式字符串？” 它还预处理模式而不是被匹配的字符串。此外，如果您查看Aho-Corasick算法，它是KMP的一般化，它构建了一个更通用的版本的此自动机，可同时处理多个模式。因此，我非常确定您正在查看KMP。