[理工] [演算法]-KMP algorithm

看板Grad-ProbAsk作者 (考驗)時間16年前 (2010/02/05 21:24), 編輯推噓2(2推 0噓 17→)
留言19則, 4人參與, 最新討論串1/1
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
→
02/05 21:28, , 1F
-1 -1 0 -1 0 1 2 3 -1 0
02/05 21:28, 1F
推
02/05 21:52, , 2F
看不懂+1
02/05 21:52, 2F
→
02/05 21:55, , 3F
t大 若我是設F(0)=0為起始的話
02/05 21:55, 3F
→
02/05 21:56, , 4F
答案是 0 0 1 0 1 2 3 4 0 1 對嗎？還是一定要-1起頭
02/05 21:56, 4F
→
02/05 22:04, , 5F
沒有規定就對，看題目怎麼問
02/05 22:04, 5F
→
02/05 22:06, , 6F
感謝
02/05 22:06, 6F
→
02/05 23:16, , 7F
那用KMP去比對字串呢? 例如搜尋abc跟他的反轉
02/05 23:16, 7F
推
02/05 23:32, , 8F
比較S1有沒有在S2裡面，先對S1做failure function
02/05 23:32, 8F
→
02/05 23:32, , 9F
接著比對兩字串，相同就向下一個字元比對，若遇到不同
02/05 23:32, 9F
→
02/05 23:34, , 10F
就查前一個相同字元的function，再根據function
02/05 23:34, 10F
→
02/05 23:35, , 11F
所給的參數J，跳回第J個字元再比對
02/05 23:35, 11F
→
02/05 23:36, , 12F
若相同，再向下比對；若還是不同再查f(i)，重複比對
02/05 23:36, 12F
→
02/05 23:36, , 13F
ex 比較 abab 跟 abcabac
02/05 23:36, 13F
→
02/05 23:37, , 14F
function 是 -1-1 0 1
02/05 23:37, 14F
→
02/05 23:37, , 15F
比對 前兩個相同 到C的時候不同，查前一個function，為-1
02/05 23:37, 15F
→
02/05 23:38, , 16F
所以從c開始再從頭比對，不同，所以向下一個字元
02/05 23:38, 16F
→
02/05 23:39, , 17F
接下來aba相同，c不同，查前一個function為 0
02/05 23:39, 17F
→
02/05 23:40, , 18F
因此再拿C跟0的下一個字元b比較，又不同，查function為-1
02/05 23:40, 18F
→
02/05 23:40, , 19F
再重頭比較
02/05 23:40, 19F
‣ 更多 lwtistunning 的文章
文章代碼(AID): #1BR1lsse (Grad-ProbAsk)