Find the longest palindrome in a string

palindrome_finder.rb

#
# Finds the longest palindrome in a string
# Works for palindromes of both even and odd length
# Has O(n^2) runtime, which is not the fastest
# Manacher's algorithm promises O(n) time
# 
# Odd length example: "ABCBAHELLOHOWRACECARAREYOUILOVEUEVOLIIAMAIDOINGGOOD"
# Result: 'ILOVEUEVOLI'
#
# Even length example: "forgeeksskeegfor"
# Result: 'geeksskeeg'
class PalindromeFinder

  PAD_CHAR = '#'

  attr_accessor :string, :results

  def initialize(string)
    self.results = {}
    self.string = string
    transform_string if even_string?
  end

  def find_longest      
    string.chars.each_with_index do |char, i|             
      matches = 0
      step_from_center = 1
      
      while match?(i, step_from_center)
        matches += 1
        step_from_center += 1
      end

      results[i] = matches
    end

    output_longest
  end


  private

  def even_string?
    string.size % 2 == 0
  end

  def transform_string
    self.string = string.chars.map{|c| [c, PAD_CHAR] }.flatten.unshift(PAD_CHAR).join
  end

  def match?(i, step_from_center)
    left_ndx = i - step_from_center
    right_ndx = i + step_from_center
    left_ndx >= 0 && right_ndx < string.size && string[left_ndx] == string[right_ndx]
  end

  def longest_result
    @longest_result ||= results.max{|r1, r2| r1[1] <=> r2[1] }
  end

  def output_longest    
    start_char = longest_result[0] - longest_result[1]
    end_char = longest_result[0] + longest_result[1]
    palindrome = string[start_char..end_char]
    palindrome.gsub!(PAD_CHAR, '') if palindrome.include?(PAD_CHAR)
    puts "The longest palindrome is '#{palindrome}'"
  end

end