BZOJ 2946 [Poi2000] 公共串


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2946

题意:给出几个由小写字母构成的单词,求它们最长的公共子串的长度。


对这几个串建立广义后缀自动机,把每个串插进去爬一下,暴力往上跳 fail 更新... 为经过的节点累加次数,如果一个节点被经过了 n 次则是合法的公共子串,对 mx 取一下 max 即可。

neither 说复杂度 看起来 是科学的...

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 2946 [Poi2000] 公共串


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,