后缀自动机伪代码

p=0

extend(c)
{
	new np;
	np.max=++L;
	for (i=p;trans[i][c]==null&&i!=null;i=parent[i])
	 trans[i][c]=np;
	if (i==null)
	   trans[np]=root
    else 
      q=i.trans[c]
    if (q.max==i.max+1)
       np.parent=q;
    else new nq
         nq.trans[]=q.trans[]
         nq.parent=q.parent
         q.parent=np.parent=nq
         nq.max=i.max+1
         for (;i.trans[c]==q;i=i.parent)
             i.trans[c]=nq
    p=np
}