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

发布于 2019-04-13  44 次阅读


题目链接

题解

题目大意:给两个串,S,T,问S中有多少个子串与T的差异是在3个字符以内的。

这道题解法有很多,像什么SAM,FFT,NTT之类的,然而我只会哈希orz

二分找它们的最长公共前缀,最多能跳3次,没了……

设N为S的长度,M为T的长度
时间复杂度 $O((N-M)\times (logM))$

代码


哇,你居然发现了这里!