[理工] KMP演算法

看板Grad-ProbAsk作者kaidi620 (萬能史哥)時間6年前 (2019/01/30 09:30)推噓5(5推 0噓 17→)

留言22則, 6人參與討論串1/1

之前我在板上有發過一篇關於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

01/30 10:03, 6年前 , 1^F

01/30 10:03, 1^F

→

y2j60537

01/30 10:03, 6年前 , 2^F

01/30 10:03, 2^F

→

y2j60537

01/30 10:03, 6年前 , 3^F

01/30 10:03, 3^F