作者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)