Re: [理工] [資結] failure fuction
※ 引述《cakeboy ()》之銘言：
: 請問failure fuction 要怎嚜算出來
: 例如 ababbababaa
: 請問要怎嚜算它的值呢?
: 有爬文過可是都是答案討論
: 沒有詳細作法,搞了好幾天都還不是很懂
: 所以希望有人可以幫幫我,感激不盡
failure function 的定義是
f(j) = (1) i 當 p0p1...pi = pj-i ... pj-1 pj where i < j
(2) -1 if 不存在 (1)的情況
依照原po的問題來解釋
index = 0 1 2 3 4 5 6 7 8 9 10
p = a b a b b a b a b a a
f(j) = -1 -1 0 1 -1 0 1 2 3 2 0
稍稍說明一下
當 index = 4
3 4 : b b
0 1 : a b
因為 b b ! = a b 所以 f(4) = -1
(未必要完全相同 開頭幾個相同也可 但此例中完全不相同)
當 index = 5
3 4 5 : b b a
0 1 2 : a b a
因為從5開始往回數0個的字串 = a = 由0往前數0個的字串 所以 f(5) = 0
當 index = 7
4 5 6 7 : b a b a
0 1 2 3 : a b a b
因為 從7往回數2個的字串 = a b a b = 由0往前數2個的字串 所以 f(7) = 2
希望我沒有解釋錯 有錯請指正~
也希望解釋的夠清楚XD"
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.25.179.113
※ 編輯: christianSK 來自: 114.25.176.233 (11/18 00:32)
推
11/18 21:07, , 1F
11/18 21:07, 1F
推
11/18 21:26, , 2F
11/18 21:26, 2F
→
11/18 21:27, , 3F
11/18 21:27, 3F
※ 編輯: christianSK 來自: 111.243.145.55 (11/18 22:28)
→
11/18 22:28, , 4F
11/18 22:28, 4F
推
11/19 02:01, , 5F
11/19 02:01, 5F
推
11/19 02:09, , 6F
11/19 02:09, 6F
→
11/19 10:40, , 7F
11/19 10:40, 7F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：