Haskell中的Knuth-Morris-Pratt實現 - 索引超出範圍

我已經使用維基百科的僞代碼嘗試在Haskell中編寫KMP算法。Haskell中的Knuth-Morris-Pratt實現 - 索引超出範圍

當我嘗試搜索超出模式的長度並且我似乎無法找到問題時，它會給出「索引超出範圍」我的「修復」只會毀了結果。

import Control.Monad 
import Control.Lens 
import qualified Data.ByteString.Char8 as C 
import qualified Data.Vector.Unboxed as V 

(!) :: C.ByteString -> Int -> Char 
(!) = C.index 

-- Make the table for the KMP. Directly from Wikipedia. Works as expected for inputs from Wikipedia article. 
mkTable :: C.ByteString -> V.Vector Int 
mkTable pat = make 2 0 (ix 0 .~ (negate 1) $ V.replicate l 0) 
    where 
     l = C.length pat 

     make :: Int -> Int -> V.Vector Int -> V.Vector Int 
     make p c t 
      | p >= l = t 
      | otherwise = proc 
      where 
       proc | pat ! (p-1) == pat ! c 
           = make (p+1) (c+1) (ix p .~ (c+1) $ t) 
        | c > 0  = make p (t V.! c) t 
        | otherwise = make (p+1) c (ix p .~ 0 $ t) 

kmp :: C.ByteString -> C.ByteString -> V.Vector Int -> Int 
kmp text pat tbl = search 0 0 
    where 
     l = C.length text 
     search m i 
      | m + i >= l = l 
      | otherwise = cond 
      where 
       -- The conditions for the loop, given in the wiki article 
       cond | pat ! i == text ! (m+i) 
          = if i == C.length pat - 1 
          then m 
          else search m (i+1) 
        | tbl V.! i > (-1) 
          = search (m + i - (tbl V.! i)) (tbl V.! i) 
        | otherwise 
          = search 0 (m+1) 

main :: IO() 
main = do 
    t <- readLn 
    replicateM_ t $ do 
     text <- C.getLine 
     pat <- C.getLine 
     putStrLn $ kmp text pat (mkTable pat)

來源

2016-01-14 the spectre

而不是試圖立即解決它，試圖真正理解發生了什麼。當事情不符合你的期望時，測試單個幫助函數並使用'Debug.Trace'是你的朋友。 – luqui

我做到了。這就是爲什麼我認爲問題在於模式的長度與字符串的長度有關。也許我誤解了，但T [i]處的表格T包含了我在模式上的部分匹配的長度，所以如果我把T [i]放在我的位置，我有時候會是長度的模式，所以我超過了長度。 –

簡單的解決方案：我混淆了m和我在kmp的最後一個條件。

| otherwise = search 0 (m+1)

變爲

| otherwise = search (m+1) 0

而且問題得到解決。

除此之外，有必要在ST monad中使用unboxed數組，否則表生成時間會非常荒謬。

來源

2016-01-15 00:07:35

Haskell中的Knuth-Morris-Pratt實現 - 索引超出範圍

回答

相關問題