之前我在板上有发过一篇关于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大详细教学><