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

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