Skip to content

Instantly share code, notes, and snippets.

@gtd
Created October 8, 2010 23:09
Show Gist options
  • Save gtd/617715 to your computer and use it in GitHub Desktop.
Save gtd/617715 to your computer and use it in GitHub Desktop.
class PalindromeFinder
def initialize(string)
@input = string
end
def longest
max, out = 0, ''
@input.chars.to_a.each_index do |i|
index, length = max_palindrome(i)
max, out = [length, @input[index, length]] if length > max
end
out
end
private
init_max = {"even" => 0, "odd" => 1}
init_b = {"even" => 1, "odd" => 2}
%w(even odd).each do |type|
define_method "max_#{type}" do |a, b, max|
max ||= init_max[type]
b ||= a + init_b[type]
if @input[a] == @input[b] && a > 0 && b <= @input.size-1
send "max_#{type}", a-1, b+1, max + 2
elsif @input[a] == @input[b]
[a, max + 2]
elsif @input[a] != @input[b]
[a+1, max]
end
end
end
def max_palindrome(i)
[max_even(i, nil, nil), max_odd(i, nil, nil)].max{ |a,b| a.last <=> b.last }
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment