#
# Normalize a string:
# - Convert letters to lowercase
# - Replace any non-letter with a space
#
def normalize(text)
text.chars.map { |ch| ch.match?(/[A-Za-z]/) ? ch.downcase : " " }.join
end
#
# Extract words from a string.
#
def extract_words(text)
normalize(text).split(/\s+/)
end
#
# Compute the common prefix between two strings.
#
def common_prefix(a, b)
limit = [a.length, b.length].min
idx = 0
idx += 1 while idx < limit && a[idx] == b[idx]
a[0...idx]
end
#
# Find the longest shared prefix among ANY subset of words.
#
def longest_shared_prefix(text)
words = extract_words(text)
return ["", 0, 0, []] if words.empty?
best_prefix = ""
best_group = []
# Compare every pair of words
words.combination(2).each do |w1, w2|
prefix = common_prefix(w1, w2)
next if prefix.empty?
# Find all words sharing this prefix
group = words.select { |w| w.start_with?(prefix) }
# Update best result
if prefix.length > best_prefix.length
best_prefix = prefix
best_group = group
end
end
[best_prefix, best_prefix.length, best_group.length, best_group]
end
#
# Main execution
#
s = "The Lowly inhabitants of the lowland were surprised to see the lower branches of the trees."
prefix, prefix_len, group_count, group_words = longest_shared_prefix(s)
puts "Longest shared prefix:"
puts "#{prefix} | prefix_len=#{prefix_len} | group_count=#{group_count} | #{group_words.inspect}"
=begin
run:
Longest shared prefix:
lowl | prefix_len=4 | group_count=2 | ["lowly", "lowland"]
=end