[問題] Knuth-Morris-Pratt algorithm
自學KMP演算法，
可是kmp最重要的failure function(也就是以下的kmp_table)一直看不懂
ref http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
問題：
亮黃色的地方，如果caseI不成立，
為什麼不是assign cnd=0
然後跑到caseIII就好了呢？
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 is less than the length of W, do:
(first case: the substring continues)
if W[pos - 1] = W[cnd],
let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1
(second case: it doesn't, but we can fall back)
otherwise, if cnd > 0, let cnd ← T[cnd]
(third case: we have run out of candidates. Note cnd = 0)
otherwise, let T[pos] ← 0, pos ← pos + 1
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.225.172
推
06/04 23:13, , 1F
06/04 23:13, 1F
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
