题意：DNA序列，在母串s中匹配模式串t，对于s中每个位置i，只要s[i-k]到s[i+k]中有c就认为匹配了c。求有多少个位置匹配了t

---

预处理\(f[i][j]\)表示位置i可以匹配字符j

分别考虑每一个字符c，对s的每个位置i求出用\(s[i,i+m-1]\)匹配t，这个字符匹配了几次

用\(a_i=[s的位置i匹配c]，\ b_i=[t_i=c]\)

那么c的匹配次数就是\(c_j=\sum\limits_{i=0}^{m-1}a_{j+i}b_i\)，位置i匹配了t当且仅当四种字符的匹配次数和等于t的长度m

这时候就可以考虑bitset暴力过了

一个常用技巧是，反转模式串(或母串)，然后就成了卷积的形式：

\[ c_j=\sum\limits_{i=0}^{m-1}a_{j+i}b_{m-1-i}=D_{m+j-1} \]

这样计算是没有问题的，因为b只有\([0,m-1]\)有值其他地方为0

注意处理每个字符前memset a和b！！！！！

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;const int N=(1<<20)+5, INF=1e9;const double PI=acos(-1);inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}struct meow{    double x, y;    meow(double a=0, double b=0):x(a), y(b){}};meow operator +(meow a, meow b) {return meow(a.x+b.x, a.y+b.y);}meow operator -(meow a, meow b) {return meow(a.x-b.x, a.y-b.y);}meow operator *(meow a, meow b) {return meow(a.x*b.x-a.y*b.y, a.x*b.y+a.y*b.x);}meow conj(meow a) {return meow(a.x, -a.y);}typedef meow cd;namespace FFT{    int n, rev[N];    void ini(int lim) {        n=1; int k=0;        while(n
         
          >1]>>1) | ((i&1)<<(k-1)); } void dft(cd *a, int flag) { for(int i=0; i
          
           >1; cd wn = meow(cos(2*PI/l), flag*sin(2*PI/l)); for(cd *p=a; p!=a+n; p+=l) { cd w(1, 0); for(int k=0; k