题意

每次询问两个单词某两位为结尾的前缀的最大后缀,且这个后缀为某个单词的前缀。

分析

考虑把所有单词的前缀作为一个单词插入AC自动机。

利用 fail 树的性质,如果\(y\)是\(x\)的孩子,则\(y\)是\(x\)的后缀。

所以两个单词的最大公共后缀就是他们的 lca 。

这套题目特殊的,除了 root ,所有的结点都是一个合法的单词结尾。

所以用 fail 指针或者 last 指针建出来的树是一样的,如果不满足上面这个性质的话,应该要用 last 来建树,这样可以保证树上的结点都是一个合法的单词结尾。

于是AC自动机跑出 fail 以后,倍增获取 lca 就行了,有点卡内存。

 


发表评论

电子邮件地址不会被公开。 必填项已用*标注