Given an arbitrary string (without spaces), print out all substrings that are palindromes

substring_palindromes.rb

# Given an arbitrary string (without spaces), print out all substrings that are palindromes

def generate_random_string(n)
  n.times.map { rand(97..122).chr }.join
end

# SLOW SOLUTION

def all_substrings(chars)
  len = chars.length
  for i in 0..(len - 2)
    for j in (i+1)..(len - 1)
      yield chars[i..j]
    end
  end
end

# 1. generate all substrings (n-squared)
# 2. check if each substring is a palindrome (slow)
def palindrome_substrings_slow(chars)
  all_substrings(chars) do |substr|
    if substr[0] == substr[-1] && substr.reverse == substr
      yield substr
    end
  end
end

# FAST SOLUTION

# pivot over each character linearly (O(n))
# examine characters surrounding pivot to check for possible palindromes (reasonably fast)
def palindrome_substrings_fast(chars)
  for i in 0..(chars.length - 1)
    examine(chars, i, i+1) { |a| yield a }
    examine(chars, i-1, i+1) { |a| yield a }
  end
end

def examine(chars, i, j)
  n = 0
  while chars[i-n] == chars[j+n]
    yield chars[i-n..j+n]
    n += 1
  end
end

rand_str = generate_random_string(2000)

subs1 = []; palindrome_substrings_slow(rand_str) { |a| subs1 << a }
subs2 = []; palindrome_substrings_fast(rand_str) { |a| subs2 << a }

puts (subs1 - subs2).inspect # ensure empty array
puts (subs2 - subs1).inspect # ensure empty array

puts "Total palindromes (slow): #{subs1.size}"
puts "Total palindromes (fast): #{subs2.size}"