BZOJ 2946 [Poi2000] 公共串

发布于 2018-01-04  133 次阅读


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

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


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

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

 


一个非常弱的准退役OIER