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