如果你只是寻找最大的回文子串，这里有一个快速和肮脏的解决方案.

def longest_palindrome(string, size)
  string.size.times do |start| # loop over the size of the string
    break if start + size > string.size # bounds check

    reverse = string[start, size].reverse

    if string.include? reverse #look for palindrome
      return reverse #return the largest palindrome
    end
  end
  longest_palindrome(string, size - 1) # Palindrome not found, lets look for the next smallest size 
end

def longest_palindrome(string)
  longest = ''
  i = 0
  while i < string.length
    j = 1
    while (i + j) <= string.length
      x = string.slice(i, j)
      if (x.length > longest.length) && (x == x.reverse)
        longest = x
      end
      j += 1
    end
    i += 1
  end
  longest
end

切片方法对于解决这个问题很方便。用经典的双while循环方法测试每个子字符串，其中(i, j)分别表示子字符串的起始索引和长度。
String#slice方法的工作方式如下：

"bdehannahc".slice(3, 8) == "hannah" # which is a palindrome and would be 
                                     # found by the method introduced above

这个函数检查整个字符串str是否是回文，如果是，我们就完成了;如果不是，则检查所有长度为str.size-1的子串，如果有一个是回文，则结束;如果不是，则检查长度为str.size-1子串，依此类推。

def longest_palindrome(str)
  arr = str.downcase.chars
  str.length.downto(1) do |n|
    ana = arr.each_cons(n).find { |b| b == b.reverse }
    return ana.join if ana
  end
end

longest_palindrome "abcdxyzyxabcdaaa"
  #=> "xyzyx"
longest_palindrome "abcdefghba"
  #=> "a"

这里的关键方法是Enumerable#each_cons。

最长回文子串：复杂度O（n）**
随附基准

# @param {String} s
# @return {String}
def longest_palindrome(s)
  return "" if s.empty?

  chars = s.chars.zip(s.size.times.map { "|" }).flatten.unshift("|")
  n = chars.size

  p_len = Array.new(3, n)
  p_len[0] = 0
  p_len[1] = 1

  max_len, max_len_pos = 0, 0

  center = 1
  right = 2

  2.step(n - 1).each do |i|   # want to use enumerator; n.times.drop(2) makes (n-2) length array
    mirror = 2 * center - i
    diff = right - i

    expand = false

    if 0 < diff
      len = p_len[mirror]

      if len < diff
        p_len[i] = len

      elsif len == diff && i == n - 1
        p_len[i] = len

      elsif len == diff && i < n - 1
        p_len[i] = len
        expand = true

      elsif diff < len
        p_len[i] = diff
        expand = true

      end
    else
      p_len[i] = 0
      expand = true
    end

    if expand
      while (i + p_len[i]) < n && 0 < (i - p_len[i]) && (not_boundary_char(p_len, i) || same_char?(chars, p_len, i))
        p_len[i] += 1
      end
    end

    if max_len < p_len[i]
      max_len = p_len[i]
      max_len_pos = i
    end

    if i < i + p_len[i]
      center = i
      right = i + p_len[i]
    end
  end

  first = (max_len_pos - max_len) / 2
  last = first + max_len - 1
  s[first..last]
end

def not_boundary_char(p_len, i)
  (i + p_len[i] + 1) % 2 == 0
end

def same_char?(chars, p_len, i)
  chars[i - p_len[i] - 1] == chars[i + p_len[i] + 1]
end

def longest_palindrome1(s)
  arr = s.chars
  s.length.downto(1) do |n|
    ana = arr.each_cons(n).find { |b| b == b.reverse }
    return ana.join if ana
  end
end

# ********************#
#     Benchmark       #
# ********************#

require "benchmark"

s = "anugnxshgonmqydttcvmtsoaprxnhpmpovdolbidqiyqubirkvhwppcdyeouvgedccipsvnobrccbndzjdbgxkzdbcjsjjovnhpnbkurxqfupiprpbiwqdnwaqvjbqoaqzkqgdxkfczdkznqxvupdmnyiidqpnbvgjraszbvvztpapxmomnghfaywkzlrupvjpcvascgvstqmvuveiiixjmdofdwyvhgkydrnfuojhzulhobyhtsxmcovwmamjwljioevhafdlpjpmqstguqhrhvsdvinphejfbdvrvabthpyyphyqharjvzriosrdnwmaxtgriivdqlmugtagvsoylqfwhjpmjxcysfujdvcqovxabjdbvyvembfpahvyoybdhweikcgnzrdqlzusgoobysfmlzifwjzlazuepimhbgkrfimmemhayxeqxynewcnynmgyjcwrpqnayvxoebgyjusppfpsfeonfwnbsdonucaipoafavmlrrlplnnbsaghbawooabsjndqnvruuwvllpvvhuepmqtprgktnwxmflmmbifbbsfthbeafseqrgwnwjxkkcqgbucwusjdipxuekanzwimuizqynaxrvicyzjhulqjshtsqswehnozehmbsdmacciflcgsrlyhjukpvosptmsjfteoimtewkrivdllqiotvtrubgkfcacvgqzxjmhmmqlikrtfrurltgtcreafcgisjpvasiwmhcofqkcteudgjoqqmtucnwcocsoiqtfuoazxdayricnmwcg"
Benchmark.bm do |x|
  x.report("longest_palindrome: ") { longest_palindrome(s) }
  x.report("longest_palindrome1: ") { longest_palindrome1(s) }
end

# user     system      total        real
# longest_palindrome:   0.007118   0.000000   0.007118 (  0.007215)
# longest_palindrome1:   0.433382   0.055217   0.488599 (  0.512605)

下面是另一个解决方案，使用较少的Ruby特性和迭代代替递归：

def longest_palindrome(string)
  # to find the longest palindrome, start with whole thing
  substr_start = 0
  substr_length = string.length
  while substr_length > 0 # 1 is a trivial palindrome and the end case
#    puts 'substr_length is:' + substr_length.to_s
    while substr_start <= string.length - substr_length
#      puts 'start is: ' + substr_start.to_s
      if palindrome?(string.slice(substr_start,substr_length))
        puts 'found palindrome: ' + string.slice(substr_start,substr_length)
        return string.slice(substr_start,substr_length)
      end
      substr_start += 1
    end
    substr_start = 0 # inner loop ctr reset
    substr_length -= 1
  end
  puts 'null string tested?'
  return ''
end

这是wikipedia中提出的幼稚/缓慢解决方案的一个Ruby实现

def PalindromicSubstring(str)
  # slow algorithm O(n^2)
  bogus_chars = str.size.times.map { "|" }
  odd_str = str.chars.zip(bogus_chars).flatten.unshift("|").join
  str_size = odd_str.size
  longest_radius_by_center = Array.new(str_size, 0)

  str_size.times do |center|
    radius = 0
    radius += 1 while center - (radius + 1) >= 0 && center + radius + 1 < str_size && odd_str[center - (radius + 1)] == odd_str[center + radius + 1]
    longest_radius_by_center[center] = radius
  end

  max_longest_radius = longest_radius_by_center.max
  center_for_max_longest_radius = longest_radius_by_center.index max_longest_radius

  start_index = center_for_max_longest_radius - max_longest_radius
  end_index = center_for_max_longest_radius + max_longest_radius

  longest_palindrome = odd_str[start_index..end_index].tr("|", "")
  longest_palindrome.size > 2 ? longest_palindrome : "none"
end

这是马纳彻的算法

def PalindromicSubstring(str)
  # Manacher's algorithm O(n)
  bogus_chars = str.size.times.map { "|" }
  odd_str = str.chars.zip(bogus_chars).flatten.unshift("|").join
  str_size = odd_str.size
  longest_radius_by_center = Array.new(str_size, 0)

  center = 0
  while center < str_size
    radius = 0

    radius += 1 while center - (radius + 1) >= 0 && center + radius + 1 < str_size && odd_str[center - (radius + 1)] == odd_str[center + radius + 1]

    longest_radius_by_center[center] = radius

    old_center = center
    old_radius = radius
    center += 1
    radius = 0
    while center <= old_center + old_radius
      mirrored_center = old_center - (center - old_center)
      max_mirrored_radius = old_center + old_radius - center

      if longest_radius_by_center[mirrored_center] < max_mirrored_radius
        longest_radius_by_center[center] = longest_radius_by_center[mirrored_center]
        center += 1
      elsif longest_radius_by_center[mirrored_center] > max_mirrored_radius
        longest_radius_by_center[center] = max_mirrored_radius
        center += 1
      else
        radius = max_mirrored_radius 
        break
      end
    end
  end

  max_longest_radius = longest_radius_by_center.max
  center_for_max_longest_radius = longest_radius_by_center.index(max_longest_radius)

  start_index = center_for_max_longest_radius - max_longest_radius
  end_index = center_for_max_longest_radius + max_longest_radius

  longest_palindrome = odd_str[start_index..end_index].tr("|", "")
  longest_palindrome.size > 2 ? longest_palindrome : "none"
end

关于如何用Ruby的方式来做有什么建议吗？