Haskell 中的 Knuth-Morris-Pratt 实现 -- 索引越界

Question

我使用维基百科的伪代码试图在 Haskell 中编写 KMP 算法。

当我尝试搜索超出模式长度但似乎找不到问题时，它给出了 "index out of bounds"；我的 "fixes" 只是毁了结果。

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)

Answer 1

简单的解决方法：我在kmp的最后一个条件中混淆了m和i。

| otherwise = search 0 (m+1)

变成

| otherwise = search (m+1) 0

问题已解决。

除此之外，有必要在 ST monad 中使用未装箱的数组，否则 table 生成会花费大量时间。

Haskell 中的 Knuth-Morris-Pratt 实现 -- 索引越界

Knuth-Morris-Pratt implementation in Haskell -- Index out of bounds

algorithm

haskell

knuth-morris-pratt