冒泡ioa
冒泡ioa

哈希
文章归档

[TJOI2017]DNA(字符串+哈希)

题目链接 题解 题目大意:给两个串,S,T,问S中有多少个子串与T的差异是在3个字符以内的。 这道题解法有很多,像什么SAM,FFT,NTT之类的,然而我只会哈希orz 二分找它们的最长公共前缀,最多能跳3次,没了…… 设N为S的长度,M为T的长度 时间复杂度 $O((N-M)\tim…

   270   2019-04-13   去围观

[CF533F]Encoding(哈希)

题目链接 题解 哈希真的是个好东西,在O(N)预处理之后,能在O(1)的时间内枚举任意子串. 这道题我们可以考虑对每种字母进行哈希. 具体来讲,hash1[i][c]存储的是字母c的哈希值(位置) 这样处理之后,就在S串里面枚举长度为T串的子串,再枚举两种字母,如果26个字母哈希值能…

   327   2019-04-07   去围观