Knuth-Morris-Pratt in Haskell

KMP.hs

import Control.Monad
import System.IO
import Data.Array.Unboxed

import System.TimeIt

match patt s = matches 0 0 s where 
  matches j i s | j == m  = i : matches (f!j) i s
                | i == n  = []
  matches j i (c:s) = matches (back j c + 1) (i+1) (s)
  f = makeList $ (-1) : [back (f!(i-1)) c + 1 | (c,i) <- zip patt [1..]]

  patt' = makeList patt
  back j c | j == -1 || patt' ! j == c = j
           | otherwise                 = back (f ! j) c
  m = length patt
  n = length s
  -- makeList = fromList . zip [0..]
  makeList :: [a] -> Array Int a
  makeList xs = listArray (0, length xs - 1) xs

-- timeIt = id
main = do
  (p:ss) <- lines `liftM` hGetContents stdin
  forM_ ss (putStrLn.reverse.take 10)
  timeIt $ do
    putStrLn.unlines.map show$ map (match p) ss