Реализация Кнута-Морриса-Пратта в Хаскеле - Индекс за пределами

Question

Я использовал псевдокод из Википедии в попытке написать алгоритм KMP на Haskell.

Это дает "индекс вне границ", когда я пытаюсь найти за пределами длины шаблона, и я не могу найти проблему; мои "исправления" только испортили результат.

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

Простое решение: я перепутал m и i в последнем состоянии kmp.

| otherwise = search 0 (m+1)

становится

| otherwise = search (m+1) 0

И проблема решена.

Кроме того, в монаде ST необходимо использовать неупакованные массивы, иначе генерация таблицы займет абсурдное время.