什么是背后KMP模式的理论匹配算法？ [英] What is the theory behind KMP pattern matching algorithm?

问题描述

什么是KMP模式匹配算法的理论基础是什么？

What is the theoretical basis of KMP pattern-matching algorithm?

据我所知，算法本身，但不理解高德纳，莫里斯和普拉特究竟是怎么创造这个算法。

I understand the algorithm itself, but, don't understand how did Knuth, Morris and Pratt invent this algorithm.

有没有任何数学证明？

你能不能给一个链接吗？

Can you give a link please?

推荐答案

在KMP匹配算法是基于有限自动机和作品含蓄地建立过渡表的，该字符串匹配自动机。使用要搜索的字符串的一个很聪明的线性时间preprocessing，匹配自动机可以被构造，并且自动机然后可以模拟在字符串线性时间搜索中。最终结果是一个线性时间算法串匹配

The KMP matching algorithm is based on finite automata and works by implicitly building the transition table for an automaton that matches the string. Using a very clever linear-time preprocessing of the string to search for, a matching automaton can be constructed, and the automaton can then be simulated on the string to search in in linear time. The net result is a linear-time algorithm for string matching.

这真实通过具有对于已匹配迄今字符串的各量的一种状态构成作品的自动机。缺省情况下，转换是这样的，相匹配的下一个字符前进到在机器的下一个状态，并读取无效字符转换回到起点。然而，某些部分的字符串来搜索可能共享一些重叠结构，所以一些新跃迁补充，采取自动机到早期（而不是第一）状态时的字符被读出。

The automaton that's constructed works by having one state for each amount of the string that has been matched so far. By default, the transitions are such that matching the next character advances to the next state in the machine and reading an invalid character transitions back to the beginning. However, certain pieces of the string to search for might share some overlapping structure, so some new transitions are added that take the automaton back to an earlier (but not the first) state when a character is read.

此算法由阿霍Corasick算法，它建立一个更复杂的自动机，以搜索多个字符串一次一概而论。

This algorithm is generalized by the Aho-Corasick algorithm, which builds a more complex automaton in order to search for multiple strings at once.

我的 该算法在我的个人网站实施 ，它包含的算法如何工作的，包括正确性证明，该算法背后更正式的直觉，以及如何获得从基本原理，算法解释实际的细节进行了广泛的讨论。我花了一段时间来放在一起，但我希望，这可能是更多地了解该算法的一个很好的资源。

I have an implementation of this algorithm on my personal site that contains an extensive discussion of the actual details of how the algorithm works, including a correctness proof, more formal intuition behind the algorithm, and explanation of how to derive the algorithm from first principles. It took me a while to put together, but I hope that it might be a good resource to learn more about the algorithm.

希望这有助于！

这篇关于什么是背后KMP模式的理论匹配算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！