gistfile1.txt

For an arbitrary string, detect the largest palindrome* present within it.
* a sequence of characters the same forwards and backwards at least 3 characters long.

For instance in "abbabcdedc", the longest palindrome would be "cdedc".

Answers?

Here's something in Haskell. I tried to decompose the problem into 1. make substrings, 2. filter out non palindromes, then 3. find the longest string. substrings time complexity grows like a Trianglular number. I think palindrome and longest are both O(n).

Usage: longest (palindromes "abbabcdedc")

    substrings []     = []
    substrings (x:xs) = decTail (x:xs) ++ substrings xs
      where
        decTail []       = []
        decTail (y:ys)   = [y] : [ (y:z) | z <- decTail ys ]

    longest []     = []
    longest (w:ws) = if length w > length w' then w else w' where w' = longest ws

    palindromes w = [ s | s <- substrings w, s == reverse s ]