Re: [理工] [資結] failure fuction

[christianSK (AG)]

※ 引述《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)
推 cakeboy:不過答案是-1 -1 0 1 -1 0 1 2 3 2 0
推 volleyer:4567 是baba喔  原PO可能不小心key錯了 整體概念是對的
→ volleyer:f(7)和f(9)都是2沒錯
※ 編輯: christianSK     來自: 111.243.145.55       (11/18 22:28)
→ christianSK:更正了~ 不好意思XD"
推 a016258:原PO帥哥
推 compulsory:推!
→ christianSK:a大別亂推...