[CF533F]Encoding(哈希)

发布于 2019-04-07  81 次阅读


题目链接

题解

哈希真的是个好东西,在O(N)预处理之后,能在O(1)的时间内枚举任意子串.
这道题我们可以考虑对每种字母进行哈希.
具体来讲,hash1[i][c]存储的是字母c的哈希值(位置)

这样处理之后,就在S串里面枚举长度为T串的子串,再枚举两种字母,如果26个字母哈希值能够相等,那么这样的变化是没问题的

时间复杂度 $O(N\times 26\times 26)$

这里进制为131,模数为 $2^{64}$

代码


哇,你居然发现了这里!