class Regexp

# File lib/regexp_optimized_union.rb, line 131
def self.optimized_union a, opts=nil
  trie = OptimizeTrie.new
  term_nodes = {}

  # build trie
  a.each do |s|
    next if s.empty?
    s = s.encode 'utf-8'
    t = trie
    s.chars.each do |c|
      c = Regexp.escape c
      unless t[c]
        t[c] = OptimizeTrie.new
      end
      t = t[c]
    end
    term_nodes[t] = true
    t.opt_maybe = true
  end

  # tag opt_suffix nodes
  term_nodes.each do |node, _|
    next unless node.empty?
    while node = node.parent and !node.opt_suffix and !node.opt_maybe
      if node.size > 1
        if node.values.all?(&:single_branch?)
          node.opt_suffix = true
        end
        break
      end
    end
  end

  Regexp.new trie.to_re_src, opts
end