Haskell'deki Knuth-Morris-Pratt algoritması

Question

Haskell'deki Knuth-Morris-Pratt algoritmasının bu uygulamasının anlaşılmasında bir sorunum var.

http://twanvl.nl/blog/haskell/Knuth-Morris-Pratt-in-Haskell

Özellikle ben otomat inşaatı anlamıyorum. Bunu inşa etmek için "Düğüm Bağlama" yöntemini kullandığını biliyorum, ama bana göre net değil ve neden doğru karmaşıklığa sahip olduğunu da bilmiyorum. Bilmek istediğim başka bir şey de, bu uygulamanın Aho-Corasick algoritmasını uygulamak için kolayca genelleştirilebileceğini düşünmenizdir.

Yanıtlarınız için teşekkürler!

Answer 1

Yani burada algoritma var: o Kullanılması

makeTable :: Eq a => [a] -> KMP a 
makeTable xs = table 
    where table = makeTable' xs (const table) 

makeTable' []  failure = KMP True failure 
makeTable' (x:xs) failure = KMP False test 
    where test c = if c == x then success else failure c 
      success = makeTable' xs (next (failure x)) 

, en "shoeshop" için inşa masada bakalım:

makeTable "shoeshop" = table0 

table0 = makeTable' "shoeshop" (const table0) 
     = KMP False test0 

test0 c = if c == 's' then success1 else const table0 c 
     = if c == 's' then success1 else table0 

success1 = makeTable' "hoeshop" (next (const table0 's')) 
     = makeTable' "hoeshop" (next table0) 
     = makeTable' "hoeshop" test0 
     = KMP False test1 

test1 c = if c == 'h' then success2 else test0 c 

success2 = makeTable' "oeshop" (next (test0 'h')) 
     = makeTable' "oeshop" (next table0) 
     = makeTable' "oeshop" test0 
     = makeTable' "oeshop" test0 
     = KMP False test2 

test2 c = if c == 'o' then success3 else test0 c 

success3 = makeTable' "eshop" (next (test0 'o')) 
     = makeTable' "eshop" (next table0) 
     = makeTable' "eshop" test0 
     = KMP False test3 

test3 c = if c == 'e' then success4 else test0 c 

success4 = makeTable' "shop" (next (test0 'e')) 
     = makeTable' "shop" (next table0) 
     = makeTable' "shop" test0 
     = KMP False test4 

test4 c = if c == 's' then success5 else test0 c 

success5 = makeTable' "hop" (next (test0 's')) 
     = makeTable' "hop" (next success1) 
     = makeTable' "hop" test1 
     = KMP False test5 

test5 c = if c == 'h' then success6 else test1 c 

success6 = makeTable' "op" (next (test1 'h')) 
     = makeTable' "op" (next success2) 
     = makeTable' "op" test2 
     = KMP False test6 

test6 c = if c == 'o' then success7 else test2 c 

success7 = makeTable' "p" (next (test2 'o')) 
     = makeTable' "p" (next success3) 
     = makeTable' "p" test3 
     = KMP False test7 

test7 c = if c == 'p' then success8 else test3 c 

success8 = makeTable' "" (next (test3 'p')) 
     = makeTable' "" (next (test0 'p')) 
     = makeTable' "" (next table0) 
     = makeTable' "" test0 
     = KMP True test0 

Not success5 tüketilen 's' ilk kökenine nasıl kullandığını Desenden.

Şimdi, isSubstringOf2 "shoeshop" $ cycle "shoe"'u yaptığınızda olanları gözden geçirin.

test7 'p' eşleşecek şekilde başarısız olduğunda, bu e "eşleşecek şekilde denemek için geri test3 düşer o gördüğünden, success4, success5, success6 ve sonsuza aracılığıyla biz döngüsü.