Manacher's Algorithm for finding palindromic sequences in Ruby

manacher.rb

# Detect all the palindromic sequences in a given string
#
# @return [<Range>] a list of all the palindromes in the given string
def all_palindromes(string)
  preprocessed = "^#{string.chars.join("#")}$"
  palindromes = [0] * preprocessed.length
  center = 0
  right = 0
  for i in 1...preprocessed.length
    mirror = center * 2 - i
    palindromes[i] = (right > i) ? [right-i, palindromes[mirror]].min : 0
    while preprocessed[i + 1 + palindromes[i]] == preprocessed[i - 1 - palindromes[i]]
      palindromes[i] += 1
    end
    if i + palindromes[i] > right
      center = i
      right = i + palindromes[i]
    end
  end
  result = []
  palindromes.each_with_index do |length, center|
    start = center - length
    stop = center + length
    start = start / 2
    stop = (stop - 1) / 2
    next unless start < stop
    result << (start..stop)
  end
  return result
end