1

I've used the pseudocode from Wikipedia in an attempt to write a KMP algorithm in Haskell.

It's giving "index out of bounds" when I try to search beyond the length of the pattern and I can't seem to find the issue; my "fixes" have only ruined the result.

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)
4

1 回答 1

1

Simple solution: I mixed up m and i in the last condition of kmp.

| otherwise = search 0 (m+1)

Becomes

| otherwise = search (m+1) 0

And the issue is resolved.

Aside from that, it's necessary to use unboxed arrays in the ST monad or the table generation takes an absurd amount of time.

于 2016-01-15T00:07:35.270 回答