suffix-automan.rb

suffix-automan.rb

class Node
  attr_accessor :edges, :terminal, :suffix_link, :id
  def initialize
    @edges = {}
    @done = false
    @suffix_link = nil
    @id = nil
  end
  def [](char)
    @edges[char]
  end
  def []=(char, node)
    @edges[char] = node
  end
end

def append!(node, x)
  n = Node.new
  node.edges[x] = n
  node.terminal =  false
  n.terminal  = true
  s = node.suffix_link
  if (t = s&.[](x)).nil?
    n.suffix_link = node.suffix_link || node
    s[x] = n unless s.nil?
    return n
  end
  t.terminal = false
  n2 = Node.new
  n2[x] = t[x]
  begin
    t[x] = n2
  end while t = t.suffix_link
  p n2
  n2.terminal = true
  return n
end

def suffix_automan(chars)
  root = Node.new
  node = root
  chars.each do |char|
    node = append!(node, char)
  end
  suffix_id!(root)
  root
end

def suffix_id!(node, v = -1)
  return node.id unless node.id.nil?
  if node.edges.empty?
    node.id = v + 1
    return v + 1
  end
  v = node.edges.map {|k, node| suffix_id!(node)}.max
  node.id = v + 1
end

def dot_automan(node, visit = {})
  return if visit.key?(node.id)
  puts "  #{node.id} -> #{node.suffix_link.id} [style=dotted];" if node.suffix_link
  puts "  #{node.id} [shape=#{node.terminal ? 'square' : 'circle'}]"
  visit[node.id] = true
  node.edges.each do |char, next_node|
    dot_automan(next_node, visit)
    puts "  #{node.id} -> #{next_node.id} [label=\"#{char}\"];"
  end
end

def dot(node)
  puts "digraph dot {"
  puts "  rankdir=LR; overlap=false; splines=true;"
  dot_automan(node)
  puts "}"
end

chars = 'abcb'.chars

# p suffix_automan(chars)
dot(suffix_automan(chars))