作者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/cn.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