首页 > 笔记 > 后缀自动机应用总结

后缀自动机应用总结


首先做了这些题对于后缀自动机的构造又有了些理解,先啰嗦几句

构造中,我们已经得到了前x个字符的后缀自动机,现在我们要得到x+1个字符的后缀自动机,什么需要改变呢?

首先,子串[0,x+1)对应的状态不存在,应当建立一个状态来表示这个串,显然,这个状态(now)的right集合是{x+1},max=x+1

现在新建立了一个状态,我们还有两件事要干:找出能转移到这个状态的状态,建立链接;确定这个状态的min,即找到它在parent树上的父亲。

能转移到now的状态显然都是right集合包含x的状态,即pre(子串[0,L)所在的状态)及pre的祖先。

c=s[x+1]我们沿着pre往上爬,会遇到一些没有c的转移的状态,显然此时直接将c的转移连向它即可。

如果全都没有c的转移,那么now的父亲设为root,也就是说找到了now的min,为1。

否则,现在我们到了第一个含有c的转移的状态,此时pre代表红色部分的状态。

如上图,至少存在两个红色的部分,他们是相同的,且其中一个位置为x,另一个位置的下一个字符是c,(注意,红色线段以及蓝色线段的右端代表它的位置,左端代表位置减去max的地方)。设q=ch[pre][c],此时我们已经可以确定now的min了,就是pre的max+2,即now的父亲的max应该为pre的>max+1

这样,如果是图中的绿色状态,即 q的max == pre的max+1 我们就可以宣布,找到了now的父亲。然后令fa[now] = q,这样在q以及所有的祖先的right集合中插入了x+1这个位置。

如果是蓝色状态,我们不得不考虑创建一个新的节点nows使它的max为p的max+1,来作为now的父亲,所以我们令nows的max = p的max + 1, fa[now] = nows,这样之前提到的两个问题已经全部解决了,但是事实上我们需要在q这个状态的right集合中插入x+1,所以我们令fa[nows] = fa[q], fa[q] = nows,则nows这个状态表示right集合正是现在的q需要的,接下来我们把pre以及所有pre的祖先中到q的转移全部换成nows,这也要求nows和q具有相同的转移,需要memcpy(ch[nows],ch[q],sizeof ch[nows])(过继所有的儿子)

刷题顺序的话建议这样吧:

spoj1811
bzoj2946
spoj8222
bzoj2882
bzoj3998
poj1743
bzoj4566
bzoj3238
bzoj2555
luogu3809
bzoj3926
bzoj2780

还做了一些太辣鸡的题,就不往上放了。

字符串大概就告一段落了,可能要补补多项式了。。


1 COMMENT

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×