作者cyli (陷入日劇裡頭了...)
看板Prob_Solve
標題Re: [問題] 演算法的問題
時間Fri Nov 3 00:03:39 2006
※ 引述《ledia (contemplation)》之銘言：
: ※ 引述《justbike (只想咬~~)》之銘言：
: : a. Pattern Matching Problem 在O(m+n)時間內解決
: KMP, BM, suffix tree, Shift Or... 等等
: wikipedia 上應該都有
: 以下兩個沒有好解法, 除非你想用 approximation
: : b. Hamiltonian Circuit Problem
: NP-complete
: : c. Bin-Packing Problem
: NP-hard
: : 上面三題的演算法過程可以請哪位大大幫忙詳述嗎?
: : 感激不盡!!!
不好意思小弟想順便請教KMP法的問題
在找KMP法的相關資料時弄不清楚
http://www-igm.univ-mlv.fr/~lecroq/string/node8.html中,下方
的the kmpNext Table中的kmpNext[i]值 == Failure Function值嗎
??這些-1,0等等的值是怎麼比對出來的以及怎麼知道下一個比對的
開頭位置??上面寫的C Code的while (j>-1 &&...那行開始就看不懂
了...弄不懂KMP法~"~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 210.240.195.227
※ 編輯: cyli 來自: 210.240.195.227 (11/03 01:19)