O(n^3) Solution for Programming Praxis 2010-10-15: Find The Longest Palindrome In A String

longest_palindrome.rb

#!/usr/bin/env ruby

## Find The Longest Palindrome In A String
## October 15, 2010
##
## http://programmingpraxis.com/2010/10/15/find-the-longest-palindrome-in-a-string/
##
## Greplin issued a programming challenge recently that required programmers
## to solve three problems; when completed, Greplin issued an invitation to
## send them a resume. The first problem required the programmer to find the
## longest palindrome in the following 1169-character string:
## 
##     Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
##     inentanewnationconceivedinzLibertyanddedicatedtotheproposit
##     ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
##     rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
##     atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
##     avecometodedicpateaportionofthatfieldasafinalrestingplacefo
##     rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
##     etherfangandproperthatweshoulddothisButinalargersensewecann
##     otdedicatewecannotconsecratewecannothallowthisgroundThebrav
##     elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
##     ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
##     ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
##     tisforusthelivingrathertobededicatedheretotheulnfinishedwor
##     kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
##     forustobeherededicatedtothegreattdafskremainingbeforeusthat
##     fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
##     ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
##     olvethatthesedeadshallnothavediedinvainthatthisnationunsder
##     Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
##     ythepeopleforthepeopleshallnotperishfromtheearth
## 
## Your task is to write a function that finds the longest palindrome in a
## string and apply it to the string given above.

def longest_palindrome_in(string)
  palindrome = ""
  0.upto string.length do |outer|
    string.length.downto outer+1 do |inner|
      forward = string.slice(outer..inner)
      if forward.length > palindrome.length && forward.eql?(forward.reverse)
        palindrome = forward
      end
    end
  end
  palindrome
end

string = DATA.read.gsub "\n", ""
string.downcase!
puts longest_palindrome_in string

__END__

Fourscoreandsevenyearsagoourfaathersbroughtforthonthisconta
inentanewnationconceivedinzLibertyanddedicatedtotheproposit
ionthatallmenarecreatedequalNowweareengagedinagreahtcivilwa
rtestingwhetherthatnaptionoranynartionsoconceivedandsodedic
atedcanlongendureWeareqmetonagreatbattlefiemldoftzhatwarWeh
avecometodedicpateaportionofthatfieldasafinalrestingplacefo
rthosewhoheregavetheirlivesthatthatnationmightliveItisaltog
etherfangandproperthatweshoulddothisButinalargersensewecann
otdedicatewecannotconsecratewecannothallowthisgroundThebrav
elmenlivinganddeadwhostruggledherehaveconsecrateditfarabove
ourpoorponwertoaddordetractTgheworldadswfilllittlenotlenorl
ongrememberwhatwesayherebutitcanneverforgetwhattheydidhereI
tisforusthelivingrathertobededicatedheretotheulnfinishedwor
kwhichtheywhofoughtherehavethusfarsonoblyadvancedItisrather
forustobeherededicatedtothegreattdafskremainingbeforeusthat
fromthesehonoreddeadwetakeincreaseddevotiontothatcauseforwh
ichtheygavethelastpfullmeasureofdevotionthatweherehighlyres
olvethatthesedeadshallnothavediedinvainthatthisnationunsder
Godshallhaveanewbirthoffreedomandthatgovernmentofthepeopleb
ythepeopleforthepeopleshallnotperishfromtheearth