[理工] KMP演算法

[kaidi620 (萬能史哥)]

之前我在板上有發過一篇關於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://www.ptt.cc/bbs/Grad-ProbAsk/M.1548811845.A.AA1.html
→ y2j60537: 建failure function是拿p去run p 在text T找p就是拿p去
→ y2j60537: run T
→ y2j60537: run的過程跟找failure function一樣 failure function
→ y2j60537: 可
推 y2j60537: https://i.imgur.com/aC8EeFd.jpg
推 wei12f8158: q是T跟p的最大配對長度
推 skyHuan: KMP的精神就是想要利用比對過的資訊減少比對失敗的成本，
→ skyHuan: pi func找出來之後，如果比對失敗就可以直接shift到正確
→ skyHuan: 位置，不用再一個字元一個字元shift，以下面這個跑到一半
→ skyHuan: 的例子為例
→ skyHuan: https://i.imgur.com/tAGEruA.jpg
→ skyHuan: T跟P比對到失敗的時候，在失敗處前面畫一條線，前面總共
→ skyHuan: 有5個字，這時候去查pi(5)=3，意思是P5之suffix與P之pref
→ skyHuan: ix可以配對到3個字元一樣，所以直接shift到剛剛畫的那條
→ skyHuan: 線前面剩3個字元，可以發現這三個字元往上看跟還沒shift
→ skyHuan: 以前是一樣的(跟pi func得知的結果一樣)，也就是不用再
→ skyHuan: 花成本去比對前面，直接從線後面比對下去就好
推 sooge: 謝謝sky大 原本都忘了怎麼解你講完後記憶瞬間回來XD
推 skyHuan: 謝謝立宇JJ  >///<
→ kaidi620: 感謝y2大神!!太謝謝你了 小弟笨笨就是需要詳細過程感恩!
→ kaidi620: 謝謝S大!
→ kcilao110779: 推sky大詳細教學><