*我真的不会 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 endend