*我真的不会 ruby 呀*

#encoding:utf-8

#==============================================================================

# ■ Suffix_Automaton

#------------------------------------------------------------------------------

# 　后缀自己主动机。

#==============================================================================

class Suffix_Automaton

  #--------------------------------------------------------------------------

  # ● 定义实例变量

  #--------------------------------------------------------------------------

  attr_reader   :total                   # 当前 SAM 中不同的子串个数

  attr_reader   :root                    # SAM 的根节点

  #==============================================================================

  # ■ State

  #------------------------------------------------------------------------------

  # 　后缀自己主动机的状态结点。

  #==============================================================================

  class State

    #--------------------------------------------------------------------------

    # ● 定义实例变量

    #--------------------------------------------------------------------------

    attr_accessor   :par                     # parent 树中的父结点

    attr_accessor   :go                      # go

    attr_accessor   :val                     # val

    #--------------------------------------------------------------------------

    # ● 初始化状态结点

    #--------------------------------------------------------------------------

    def init(val = 0)

      @par = nil

      @go = []

      @val = val

      for i in 0..26 do

        @go[i] = nil

      end

    end

    #--------------------------------------------------------------------------

    # ● 计算结点表示的不同子串数

    #--------------------------------------------------------------------------

    def calc

      return 0 if @par == nil

      return @val - @par.val

    end

  end

  #--------------------------------------------------------------------------

  # ● 初始化后缀自己主动机

  #--------------------------------------------------------------------------

  def initSAM

    @total = 0

    @cur = 0

    @nodePool = []

    @root = newState

    @last = @root

  end

  #--------------------------------------------------------------------------

  # ● 创建新的状态结点

  #--------------------------------------------------------------------------

  def newState(val = 0)

    @nodePool[@cur] = State.new

    @nodePool[@cur].init(val)

    @cur += 1

    return @nodePool[@cur-1]

  end

  #--------------------------------------------------------------------------

  # ● 加入字符

  #--------------------------------------------------------------------------

  def extend(w)

    p = @last

    np = newState(p.val + 1)

    while p != nil and p.go[w] == nil do

      p.go[w] = np

      p = p.par

    end

    if p == nil

      np.par = @root

      @total += np.calc # 统计

    else

      q = p.go[w]

      if p.val + 1 == q.val

        np.par = q

        @total += np.calc # 统计

      else

        nq = newState(p.val + 1)

        for i in 0..26 do

          nq.go[i] = q.go[i]

        end

        @total -= q.calc # 统计

        nq.par = q.par

        q.par = nq

        np.par = nq

        @total += q.calc + nq.calc + np.calc

        while p != nil and p.go[w] == q do

          p.go[w] = nq

          p = p.par

        end

      end

    end

    @last = np

  end

end