P5028 Annihilate

时间:2022-05-20 12:57:19

P5028 Annihilate

50个串,任意两两的最长公共子串

回忆最长公共子串求法

1.hash+二分

2.SAM

3.SA,属于不同的串的hei的max

1.hash+二分

暴力两两枚举再跑的话直接TLE

2.SAM

卡空间64MB跑不过去

3.SA

P5028 Annihilate

其实就是两个最长公共子串的扩展

每个i位置,枚举所有的n个最后一个位置,RMQ求LCP更新答案

由于相邻的最大,所以答案一定可以枚举到。

相关文章