【bzoj2946】[Poi2000]公共串

2015年4月21日2,6851

Description

       给出几个由小写字母构成的单词,求它们最长的公共子串的长度。
任务:
l        读入单词
l        计算最长公共子串的长度
l        输出结果

Input

文件的第一行是整数 n,1<=n<=5,表示单词的数量。接下来n行每行一个单词,只由小写字母组成,单词的长度至少为1,最大为2000。

Output

仅一行,一个整数,最长公共子串的长度。

Sample Input

3
abcb
bca
acbc

Sample Output

题解

后缀自动机没学清楚叫你装叉,看hzwer这个傻逼wa了多少发。。。
第一个串建自动机,每个串放进去匹配,得出每个状态的最大匹配长度
每个状态取所有串最小值,得出最大公共子串长
对所有状态子串长取最大值就是答案
叫你装叉不写哈希

 

 

  • ez_zjt2015年8月20日 下午4:22 回复

    扑通扑通跪下来

    #1