克努斯-莫里斯-普拉特算法
维基百科，自由的百科全书
Knuth–Morris–Pratt 字符串查找算法在一个主"文本字符串" S 内查找一个"词W"的出现，通过采用一种简单的观察，在不匹配发生的时候这个词自身包含足够的信息来确定下一个匹配将在哪里开始，以此越过对以前匹配的字符的重新检查。
算法是由 高德纳 和 Pratt 以及独立地由 J. H. Morris 在1977年发明的，但是三人联合发表了它。
在本文中，我们将使用始于零的数组来表示我们的字符串；所以下面例子中 W 中的 'C' 将被表示为 W[2]。一般来说，表示法服从 [[C编程语言|C]] 语法。
目录 |
[编辑] 算法说明
[编辑] 查找算法实例
让我们用一个实例来演示这个算法。在任意给定时间，本算法被两个整数m和i所决定：m代表主文字符串S内匹配字符串W的当前查找位置；i代表匹配字符串W当前做比较的字符位置。图示如下：
[编辑] 外部連結
您可以在維基教科書中查找此百科条目的相關電子教程：
- An explanation of the algorithm and sample C++ code by David Eppstein
- Knuth-Morris-Pratt algorithm description and C code by Christian Charras and Thierry Lecroq
- Interactive animation for Knuth-Morris-Pratt algorithm by Mike Goodrich
- Explanation of the algorithm from scratch by FH Flensburg.
[编辑] 外部链接
[编辑] 引用
- 高德纳; James H. Morris, Jr, Vaughan Pratt（1977年）．Fast pattern matching in strings．SIAM Journal on Computing，6（2）：323-350．
- Thomas H. Cormen，Charles E. Leiserson, Ronald L. Rivest, Clifford Stein（2001）．“Section 32.4: The Knuth-Morris-Pratt algorithm”，Introduction to Algorithms，Second edition，MIT Press and McGraw-Hill，923-931．ISBN 0262032937．
