module Algorithms.DFA.KMP where
import Data.List (mapAccumL)
import Algorithms.DFA.KMP.Automaton
import Data.List.NonEmpty (NonEmpty (..), toList)
import qualified Data.List.NonEmpty as NE
unsafeFrom :: NonEmpty (a,Index) -> NonEmpty (Interface a)
unsafeFrom ((x,0) :| []) = Interface [] (Right 0) [x] :| []
unsafeFrom ((x,0) :| xs) = Interface [(x,1)] (Right 0) [] :| core (zip [2..] xs) where
core [(_,(x,i))] = [Interface [] (Left i) [x]]
core ((n,(x,i)) : xs) = Interface [(x,n)] (Left i) [] : core xs
table :: Eq a
=> NonEmpty a
-> NonEmpty Index
table xt@(x :| xs) = (0 :| ) . snd . mapAccumL f (0, toList xt) $ xs where
f (n, z:zs) x
| x == z = ((n + 1, zs), n)
| otherwise = ((0, xs), n)
match :: Eq a
=> NonEmpty a
-> [a]
-> Bool
match p s = case run (automaton . unsafeFrom $ NE.zip <*> table $ p) s of
Nothing -> True
_ -> False
(==!) :: Eq a
=> [a]
-> [a]
-> Bool
(p:ps) ==! xs = match (p :| ps) xs