首页 > 题解 > bzoj 2946 [Poi2000]公共串

bzoj 2946 [Poi2000]公共串

Description

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

Input

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

Output

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

Sample Input

3

abcb

bca

acbc

Sample Output

题解

首先对其中的一个串建出SAM。拓扑排序一下。

每个点记录每个串最长匹配长度的最小值,最后找到所有点中最长的一个就可以了

注意有个细节。总结答案的时候,要更新一下Parent树上的节点的答案。因为匹配的时候可能是直接跳到这个节点上的,Parent有可能是没有更新的。所以要从拓扑序最大的那个开始,往前走,边走边更新答案。

那么为什么上个题不用这么更新?因为Parent树上的那个答案肯定比这个答案要小,上个题只要求最大的答案,这题因为有很多串,要全面考虑。

为什么只用更新一个Parent?不应该跳Parent树直到根?因为按照拓扑序走的,下次走到这个点的Parent的时候就会更新它的Parent了。


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×