P5546公共串题解

感觉算法没什么好讲的了,下面带领大家做题目
有以下四种做法。
KMP
哈希
SA
SAM
请大家先自行思考。
这题是放在SA的练习题上,但是作为刚学会SA的蒟蒻,没有思路,所以我们可以用更会简单的哈希。

如果思考不出请点开

前置知识:哈希。
考虑二分长度,然后在其中 n-1 个字符串中把所有长度符合的串中 map 计入下来。
然后枚举那个没有计入的串,将他符合长度的串也枚举出来,算出哈希值,然后看看其他几个字符串是否都有这个串。

下期题目大家先自行思考
https://www.luogu.com.cn/problem/P5662
照顾萌新,下期题目比,这期还要简单。

1 个赞