Atcoder abc312
https://atcoder.jp/contests/abc312/tasks/abc312_h
Ex - snukesnuke
N个字符串s[i]
1 | t = set<string> |
$\sum |S_i| \le 2\cdot 10^5$, 小写英文字母
2s
1024mb
我的思路
如果不同字符串之间互不影响,那么相同si的ki对应的值就是1,2,4,5,6,7…
那么问题就是如果不同的字符串之间有影响
$k_i\cdot s_i = k_j\cdot s_j, s_i \neq s_j$
若$k_i = 1$,也就是 $s_i$会是$s_j$的重复序列, 首先重复序列的长度一定是 $s_i$长度的因数,这样可以 额外$O(|s_i| log|s_i|)$ 的把所有处理成
$(s_i,repeat)$ 的形式
根据字符串的循环结的理论,显然 一个字符串有一个最小循环单位,且其它循环都是它的倍数
1 | 引理 简单证明 |
若 $k_i,k_j$均不为1,且$gcd(k_i,k_j) = 1$,那么用到上面引理类似的
不失一般性,设 $|s_i| > |s_j|$
1 | [s_i......][s_i......][s_i......][s_i......][s_i.....] |
综上,首先把所有的字符串拆成最小循环节和repeat, 然后对所有 最小循环结做hash
似乎就没了