[CF533F]Encoding(哈希)

题目链接

题解

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

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

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

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

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注