Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
import Data.List.Zipper as Z
main = do
let string = "yabbadabbadoo"
print $ maximum $ palindromeSizes string
-- Find the size of the largest palindrome centered at each location in
-- a string. There will be 2*n-1 locations, because we count even and odd
-- centers. Go along the zipper, checking the sizes of palindromes to the left
-- and right as we go.
palindromeSizes :: Eq a => [a] -> [Int]
palindromeSizes = sizes . Z.fromList
where sizes :: Eq a => Zipper a -> [Int]
sizes z = if Z.endp z then []
else evenSize z : oddSize z : sizes (right z)
evenSize :: Eq a => Zipper a -> Int
evenSize (Zip left (right)) = 2 * (equalPrefixLength left right)
oddSize :: Eq a => Zipper a -> Int
oddSize (Zip left (_:right)) = 2 * (equalPrefixLength left right) + 1
-- Check equal prefix length of the lists. The left list is already reversed
-- because of the Zipper.
equalPrefixLength :: Eq a => [a] -> [a] -> Int
equalPrefixLength xs ys = length $ takeWhile (uncurry (==)) $ zip xs ys
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.