之前我在板上有發過一篇關於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如何做出來的，這困擾小弟超久，想了一個小時還是無解，只好來這邊請教大神

建failure function是拿p去run p 在text T找p就是拿p去run Trun的過程跟找failure function一樣 failure function可https://i.imgur.com/aC8EeFd.jpg

q是T跟p的最大配對長度

KMP的精神就是想要利用比對過的資訊減少比對失敗的成本，pi func找出來之後，如果比對失敗就可以直接shift到正確位置，不用再一個字元一個字元shift，以下面這個跑到一半的例子為例https://i.imgur.com/tAGEruA.jpgT跟P比對到失敗的時候，在失敗處前面畫一條線，前面總共有5個字，這時候去查pi(5)=3，意思是P5之suffix與P之prefix可以配對到3個字元一樣，所以直接shift到剛剛畫的那條線前面剩3個字元，可以發現這三個字元往上看跟還沒shift以前是一樣的(跟pi func得知的結果一樣)，也就是不用再花成本去比對前面，直接從線後面比對下去就好

謝謝sky大 原本都忘了怎麼解你講完後記憶瞬間回來XD

謝謝立宇JJ >///<

感謝y2大神!!太謝謝你了 小弟笨笨就是需要詳細過程感恩!謝謝S大!

推sky大詳細教學><