KMP算法
S
W
这个
查找过程
[编辑]以W
="ABCDABD"
,S
="ABC ABCDAB ABCDABCDABDE"
为例说明查找过程。查找过程m
i
:
m
代表 主 文字 符 串 S
内 匹 配 字 符 串 W
的 当 前 查找位置 ,i
代表 匹 配 字 符 串 W
当 前 做比较的字 符 位置 。
图示如下:
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
W
S
S[3](=' ')
W[3](='D')
S[1]
S[1]~S[3]
W[0]
m = 4
以及i = 0
。
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
"ABCDAB"
這個"AB"
"ABCDAB"
"AB"
m = 8, i = 2
,
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
於m = 10
m = 11, i = 0
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
這時,S[17](='C')
W[6]
"ABCDAB"
"AB"
,m = 15
i = 2
,
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
找到S[15]
部分 匹 配 表
[编辑]S
对于W
W
W[0]
开始T[i]
W
W[i - 1]
T[0] = -1
,
创建表 算法 示 例
[编辑]以W = "ABCDABD"
为例。
T[0] = -1
。为求T[1]
,必须找到"A"
W
"A"
T[1] = 0
。类似T[2] = 0
。
继续到T[3]
,W[0..1] = W[1..2]
,则必W[0..0] = W[1..1]
。W[0..0]
W
T[2] = 1
(而有T[2] = 0
,说明
从而,T[3]=0
。
W[4] = 'A'
。'A'
这个T[4] = 0
。
现在W[5] = 'B'
,W[4]
W[5]
,W[4]
'A'
W[4]
W[5]
W[4]
。T[5] = 1
。
W[4] = 'A'
。'B'
,并且这也确实W[5]
。此外,W[6]
W[4]
,T[6] = 2
。
于是
i
|
0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
W[i]
|
A | B | C | D | A | B | D |
T[i]
|
-1 | 0 | 0 | 0 | 1 | 2 | 0 |
另一个更复杂和有趣的例子:
i
|
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
W[i]
|
P | A | R | T | I | C | I | P | A | T | E | I | N | P | A | R | A | C | H | U | T | E | ||
T[i]
|
-1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 | 0 |
建立 表 算法 的 伪代码的解 释
[编辑]algorithm kmp_table: input: an array of characters, W (the word to be analyzed) an array of integers, T (the table to be filled) output: nothing (but during operation, it populates the table) define variables: an integer, pos ← 2 (the current position we are computing in T) an integer, cnd ← 0 (the zero-based index in W of the next
character of the current candidate substring) (the first few values are fixed but different from what the algorithm
might suggest) let T[0] ← -1, T[1] ← 0 while pos < length(W) do (first case: the substring continues) if W[pos - 1] = W[cnd] then let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1 (second case: it doesn't, but we can fall back) else if cnd > 0 then let cnd ← T[cnd] (third case: we have run out of candidates. Note cnd = 0) else let T[pos] ← 0, pos ← pos + 1
建立 表 的 算法 的 效率
[编辑]W
pos
pos - cnd
在 第 一 个分支 里 ,pos - cnd
不 变,而pos
与 cnd
同 时自增 ,自然 ,pos
增加 了 。在 第 二 个分支 里 ,cnd
被 更 小 的 T[cnd]
所 替 代 ,从而增加 了 pos - cnd
。在 第 三 个分支 里 ,pos
增加 了 ,而cnd
不 变,所以 pos
和 pos - cnd
都 增加 了 。
pos ≥ pos - cnd
,pos
pos
pos = n
时终
另见
[编辑]外部 連結
[编辑]- (
英文 )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. Fast pattern matching in strings. SIAM Journal on Computing. 1977, 6 (2): 323–350 [2006-07-27]. (原始 内容 存 档于2010-01-04).
- Thomas H. Cormen; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Section 32.4: The Knuth-Morris-Pratt algorithm. Introduction to Algorithms Second edition. MIT Press and McGraw-Hill. 2001: 923-931. ISBN 978-0-262-03293-3.