maxSubPalindrome.hs

module Main where
-----------------------------------------------------------------------------
---- |
----
---- 输出最长回文子串, 直观版。
----
-------------------------------------------------------------------------------

import Data.List (maximumBy)
import Data.Function (on)

-- | 返回所有子串。
sublists :: [a] -> [[a]]
sublists [] = [[]]
sublists (x:xs) = map (x:) xss ++ xss where xss = sublists xs

-- | 判断是否是回文，即反序后和原来一样。
isPalindrome :: (Eq a) => [a] -> Bool
isPalindrome xs = xs == reverse xs

-- | 返回最长满足是回文的子串, 即从所有子串中去掉不是回文的，取最长的子串。
maxSubPalindrome :: (Eq a) => [a] -> [a]
maxSubPalindrome xs = maximumBy (compare `on` length) [ xs' | xs' <- sublists xs, isPalindrome xs' ]

main :: IO ()
main = print $ maxSubPalindrome "abcbea"