最小状态后缀自动机：

把结束集合相同的状态合在一起，增量法构造。

$AAAAxBAAAAxBAA$

$last=AAAAxBAAAAxBAA$

$last$ 祖先依次为：

$1$ 、 $BAAAAxBAA,xBAAAAxBAA,AxBAAAAxBAA,$

$AAxBAAAAxBAA,AAAxBAAAAxBAA,AAAAxBAAAAxBAA$

$2$ 、 $BAA,xBAA,AxBAA,AAxBAA,AAAxBAA,AAAAxBAA$

$3$ 、 $AA$

$4$ 、 $A$

其中 $3$ 是第一个有 $x$ 转移的节点。沿 $parent$ 树上升父亲是儿子的后缀， $maxl_{fa}+1=minl_{son}$

在后面加入 $x$ ，则前两个没有 $x$ 转移，可以直接把转移设成 $np$ 。

$q=s[p].tr[x]$ ， $q=x,Ax,AAx,AAAx,AAAAx$ 。

$q$ 代表的状态的 $Right$ 集合为 $\{5,11\}$ ，但加入 $x$ 后应变成两个节点 $x,Ax,AAx$ 和 $AAAx,AAAAx$ ， $Right$ 集合分别为 $\{5,11,15\}$ 和 $\{5,11\}$ 。让 $q$ 变成 $AAAx,AAAAx$ ，新建 $nq=x,Ax,AAx$ ，显然原来 $q$ 的 $parent$ 还是 $nq,q,np$ 的祖先，前两个因为是一个串分裂出来的，只是 $right$ 比原来多了最后一位，而 $q$ 的 $parent$ 的 $right$ 集合一定也多了最后一位，所以 $parent[q]$ 是他们所有的祖先，因为 $nq$ 代表原来 $q$ 能放在后缀的部分，所以一定是 $q$ 的短的几个，而新的 $q$ 代表了原来的 $q$ 除去 $nq$ 之外较长的几个，也就是说 $nq$ 是 $q$ 的后缀且 $maxl_{nq}+1=minl_q$ ，所以一定有 $par_q=nq$ ， $np$ 也是 $right$ 集合包含 $n+1$ 的状态中 $maxl$ 最p大的一个，所以 $par_{np}=nq$ 。