manacher.hs

module Main where
import qualified Data.Vector as V
import Data.Maybe
import Data.Ord

-- manacher algorithm
-- $ ghci
-- $ :l manacher.hs
-- > manacher "aba"
manacher :: String -> String
manacher arg0 =  filter (/= '|') . V.toList $  maximum'  getList
  where
    getList :: [V.Vector Char]
    getList = foreveryvchars 1 $ format arg0
    
-- get the maximum length palindrome
maximum' :: [V.Vector Char] -> V.Vector Char
maximum' = foldr1 (\x y -> if V.length x > V.length y then x else y)

-- for every character try to match the left with right side
foreveryvchars :: Int -> V.Vector Char -> [V.Vector Char]
foreveryvchars center vchars =
  case vchars V.!? center of
    Nothing -> []
    _ -> let (k, v) = match center 1 vchars
             in v : foreveryvchars
                ((\x -> if x == 0 then center + 1 else center + x) k)  vchars


-- Takes the center and radius and tries to match
-- String one at a time
match::Int -> Int -> V.Vector Char -> (Int, V.Vector Char)
match center radius vchars = let left = getleft center radius vchars
                                 right = getright center radius vchars
                                 in
                               case left /= Nothing && right /= Nothing && left == right of
                                 True -> match center (radius + 1) vchars
                                 _ -> (radius - 1, V.slice (center - (radius - 1) ) (1 + ((radius -1 ) * 2)) vchars)
                                   
getleft center radius vchars = vchars V.!? (center - radius)
getright center radius vchars = vchars V.!? (center + radius)

-- 
format :: String -> V.Vector Char
format = stov . convert

-- Insert pipe after each character
convert::String -> String
convert [] = '|':[]
convert (x:xs) = '|':x:convert xs

-- Convert String to Data.Vector
stov::String -> V.Vector Char
stov = V.fromList

main::IO()
main = print "hello world"