作者lwtistunning (考验)
看板Grad-ProbAsk
标题[理工] [演算法]-KMP algorithm
时间Fri Feb 5 21:24:03 2010
Fill the function value in KMP algorithm for string matching
J 0 1 2 3 4 5 6 7 8 9
pattern a b a c a b a c d a
failure(j)
请问有高手能教一下吗 谢谢！！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 220.139.132.251
1F：→ taitin:-1 -1 0 -1 0 1 2 3 -1 0 02/05 21:28
2F：推 assassin88:看不懂+1 02/05 21:52
3F：→ lwtistunning:t大 若我是设F(0)=0为起始的话 02/05 21:55
4F：→ lwtistunning:答案是 0 0 1 0 1 2 3 4 0 1 对吗？还是一定要-1起头 02/05 21:56
5F：→ taitin:没有规定就对，看题目怎麽问 02/05 22:04
6F：→ lwtistunning:感谢 02/05 22:06
7F：→ polomoss:那用KMP去比对字串呢? 例如搜寻abc跟他的反转 02/05 23:16
8F：推 taitin:比较S1有没有在S2里面，先对S1做failure function 02/05 23:32
9F：→ taitin:接着比对两字串，相同就向下一个字元比对，若遇到不同 02/05 23:32
10F：→ taitin:就查前一个相同字元的function，再根据function 02/05 23:34
11F：→ taitin:所给的参数J，跳回第J个字元再比对 02/05 23:35
12F：→ taitin:若相同，再向下比对；若还是不同再查f(i)，重复比对 02/05 23:36
13F：→ taitin:ex 比较 abab 跟 abcabac 02/05 23:36
14F：→ taitin:function 是 -1-1 0 1 02/05 23:37
15F：→ taitin:比对 前两个相同 到C的时候不同，查前一个function，为-1 02/05 23:37
16F：→ taitin:所以从c开始再从头比对，不同，所以向下一个字元 02/05 23:38
17F：→ taitin:接下来aba相同，c不同，查前一个function为 0 02/05 23:39
18F：→ taitin:因此再拿C跟0的下一个字元b比较，又不同，查function为-1 02/05 23:40
19F：→ taitin:再重头比较 02/05 23:40