module Main where

import Data.Sequence as S
import Data.List as L
import Control.Monad as M
import Control.Monad.ST
import Data.Vector as V
import Data.Vector.Mutable as VM

main :: IO ()
main = return ()

rd :: Int -> MVector s Int -> ST s Int
rd c t = t `VM.read` c

newC :: Vector Char -> Int -> Int -> MVector s Int -> ST s Int
newC w p c t
  | (c >= 0) && (w!p /= w!c) = do
    nc <- next
    newC w p nc t
  | otherwise = next
  where
    next = t `VM.read` c

stepKmpBuild :: Vector Char -> MVector s Int -> Int -> Int -> ST s Int
stepKmpBuild w t c p
  | w!p == w!c = do
      cv <- t `VM.read` c
      write t p cv
      return (c + 1)
  | otherwise = do
      write t p c
      c' <- newC w p c t
      return (c' + 1)

kmpBuild w = runST $ do
  v <- VM.replicate ((V.length w) + 1) (-1)
  c <- M.foldM (stepKmpBuild w v) 0 [1..(V.length w - 1)]
  write v (V.length w) c
  freeze v

-- kmpBuild w =  snd $ L.foldl' (stepKmpBuild w) (0, S.fromList [-1]) [1..(V.length w)]

test1 :: MVector s Int -> ST s (MVector s Int)
test1 v = do
  write v 1 1
  return v

test = runST $ do
   v <- VM.replicate 10 0 ::ST s (MVector s Int)
   t <- test1 v
   freeze t