KMP by some guy on 知乎 with “tying the knot” technique

kmp.hs

{-# LANGUAGE NoMonomorphismRestriction #-}

module KMP3 (buildKMP , matchKMP , State) where

data State a =
    State (State a) (State a) a -- State next fail char
  | Aux (State a) -- Aux next
  | Finish (State a) -- Finish fail

nextOf :: Eq a => State a -> a -> State a
nextOf (State n f c) c' = if c == c' then n else nextOf f c'
nextOf (Aux n) _ = n
nextOf (Finish f) c = nextOf f c

buildKMP :: Eq a => [a] -> State a
buildKMP s = start where
  aux = Aux start
  start = buildState aux s
  buildState fail (c:cs) = State (buildState (nextOf fail c) cs) fail c
  buildState fail [] = Finish fail

matchKMP :: Eq a => State a -> [a]-> [Int]
matchKMP state s = matchKMP' [] state 0 s where
  matchKMP' es (Finish fail) i s = matchKMP' (i:es) fail i s
  matchKMP' es state i [] = es
  matchKMP' es state i (c:cs) = matchKMP' es (nextOf state c) (i + 1) cs

match = matchKMP . buildKMP