Раздел «Язык Ruby».ProblemLNEERC2007:

Задача L с полуфинала ACM ICPC

Код на Ruby, скорее всего, не проходит по времени. Но зато хорошо отображает идею решения.

class Array # играет роль вершины в Боре
  # является ли вершина конечной?
  attr_accessor :final

  # добавить новое слово в бор
  def add(word)
    bor = self
    word.each_byte do |b|
      b -= ?a
      bor = (bor[b] ||= Array.new)
    end
    bor.final = true
  end
  
  # рекурсивно вычислить хэш поддерева,
  # запоминая все получающиеся по дороге хэши в глобальной переменной $all_hashes
  def hsh
    x = 0
    each_with_index do |v, idx|
      next unless v 
      x += (idx + 331) * ( (2*v.hsh + (final ? 117727: 17)) )
    end
    $all_hashes[x] = 1
    x
  end
end

def solve(words)
  bor = Array.new
   
  words.each do |word|
    bor.add word
  end
  
  $all_hashes = {}
  bor.hsh
  # число различных (неизоморфных) поддеревьев и есть ответ 
  puts $all_hashes.size
end

f = STDIN
# f = File.open('language.in')
f.gets
solve f.read.split