【HEOI2012】旅行问题


题意

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

分析

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

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

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

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

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

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

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 0
  • 8,102

Categories

Archive

Comments