Skip to content

Instantly share code, notes, and snippets.

@joshbuddy
Created March 24, 2012 21:39
Show Gist options
  • Save joshbuddy/2188292 to your computer and use it in GitHub Desktop.
Save joshbuddy/2188292 to your computer and use it in GitHub Desktop.
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?
@luciferous
Copy link

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 ]

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment