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

题目链接

题解

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

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

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

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

代码

发表评论

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