这是什么模式匹配算法？
我正在读《理论与实践》一书。数据结构问题（Seymour Lipschuz）。
让我提供我正在阅读的部分的图像。
。
本书的这一部分讨论一种名为“第二模式匹配算法”的模式匹配算法。
这是什么算法？这是 Boyer-Moore、KMP、Horspool 还是什么？
或者说，这是作者提出的新算法吗？
I was reading the book Theory & Problems Of Data Struc (Seymour Lipschuz).
Let me provide an image of the section I was reading..
This section of the book talks about a pattern-matching algorithm named "Second Patter-Matching Algorithm".
What algorithm is this? Is this Boyer-Moore or KMP or Horspool or what?
Or, is this any new algorithm produced by the author?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我相信这是 KMP 算法。 KMP 构建了一个“失败表”，本质上是一个自动机，它会说“如果您在某个特定字符上不匹配，那么您仍然可以匹配多少模式字符串？”它还对模式进行预处理，而不是对匹配的字符串进行预处理。此外，如果你看一下 Aho-Corasick 算法，它是 KMP 的推广，它构建了这个自动机的更通用版本，可以同时处理多种模式。因此，我很确定您正在考虑 KMP。
I believe that this is the KMP algorithm. KMP constructs a "failure table" that is essentially an automaton saying "if you mismatch on a particular character, how much of the pattern string can you still be matching?" It also does a preprocessing of the pattern and not the string being matched. Moreover, if you look at the Aho-Corasick algorithm, which is a generalization of KMP, it constructs a more general version of this automaton that works on multiple patterns at once. Consequently, I'm pretty sure that you're looking at KMP.