作者kaidi620 (萬能史哥)
看板Grad-ProbAsk
標題[理工] KMP演算法
時間Wed Jan 30 09:30:43 2019
之前我在板上有發過一篇關於KMP演算法的
當時有大神請我看影片，但我好像怎麼都找不到關於run主要字串的影片，
都只有看到如何建立failure function的影片。
想問一下大神 如果是 T= a a b a b b a b a b b b a b a b b a a a b b
p= a b a b b a a a
1 2 3 4 5 6 7 8
prefix function= p[i] a b a b b a a a
π[i] 0 0 1 2 0 1 1 1
答案是 i= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
T= a a b a b b a b a b b b a b a b b a a a b b
p= a b a b b a a a
q= 1 1 2 3 4 5 6 2 3 4 5 0 1 2 3 4 5 6 7 8 2 0
想問的是q如何做出來的，這困擾小弟超久，想了一個小時還是無解，只好來這邊請教大神
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.1.102
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1548811845.A.AA1.html
1F：→ y2j60537: 建failure function是拿p去run p 在text T找p就是拿p去 01/30 10:03
2F：→ y2j60537: run T 01/30 10:03
3F：→ y2j60537: run的過程跟找failure function一樣 failure function 01/30 10:03
4F：→ y2j60537: 可 01/30 10:03
6F：推 wei12f8158: q是T跟p的最大配對長度 01/30 10:16
7F：推 skyHuan: KMP的精神就是想要利用比對過的資訊減少比對失敗的成本， 01/30 10:20
8F：→ skyHuan: pi func找出來之後，如果比對失敗就可以直接shift到正確 01/30 10:20
9F：→ skyHuan: 位置，不用再一個字元一個字元shift，以下面這個跑到一半 01/30 10:20
10F：→ skyHuan: 的例子為例 01/30 10:20
12F：→ skyHuan: T跟P比對到失敗的時候，在失敗處前面畫一條線，前面總共 01/30 10:20
13F：→ skyHuan: 有5個字，這時候去查pi(5)=3，意思是P5之suffix與P之pref 01/30 10:20
14F：→ skyHuan: ix可以配對到3個字元一樣，所以直接shift到剛剛畫的那條 01/30 10:20
15F：→ skyHuan: 線前面剩3個字元，可以發現這三個字元往上看跟還沒shift 01/30 10:20
16F：→ skyHuan: 以前是一樣的(跟pi func得知的結果一樣)，也就是不用再 01/30 10:20
17F：→ skyHuan: 花成本去比對前面，直接從線後面比對下去就好 01/30 10:20
18F：推 sooge: 謝謝sky大 原本都忘了怎麼解你講完後記憶瞬間回來XD 01/30 11:41
19F：推 skyHuan: 謝謝立宇JJ >///< 01/30 11:43
20F：→ kaidi620: 感謝y2大神!!太謝謝你了 小弟笨笨就是需要詳細過程感恩! 01/30 19:21
21F：→ kaidi620: 謝謝S大! 01/30 19:22
22F：→ kcilao110779: 推sky大詳細教學>< 01/30 23:19