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?

Up to you, I just wanted to see what other people thought. Was the question too silly?

…

On 2012-03-24, at 15:08, Oliver ***@***.*** wrote: haha, want me to delete that comment so other people can guess without my pre-disposing them? --- Reply to this email directly or view it on GitHub: https://gist.github.com/2188292

It's pretty Computer Science-y. I thought it might be NP-hard. Looks like there's a linear time solution http://en.wikipedia.org/wiki/Longest_palindromic_substring

not too efficient but short:

def largest_palindrome(s)
  (s.split /\s/).map {|x| x.length}.max.downto(1).each do |x|
    re = ("(\\w)" * x) + "\\w?"
    x.downto(1).each { |y| re += "\\#{y}" }
    s.match(re) { |z| return z }
  end
end

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 ]