D. Fuzzy Search

fft下标一定要从0开始,不然特麻烦
观察题目容易发现,可以在O(n)时间内判断对于位置i是否能在[i-k,i+k]区间存在 A G C T
然后得到一个O(n*m)的算法,考虑优化
那么分开考虑 A G C T,令s[i]表示在第i个位置匹配到了多少字母。
s[i] = \sum_{j=1}^m k[i-j]*t[j]其中k[i]表示第i个位置是否能匹配到某一个字母
类似于某个字符串匹配的题一样 ,t数组还是要取反。
然后fft即可,注意要四舍五入,复杂度O(n\log n)
c++代码如下:

 

5 + 1 =