\(1.\)定义匹配函数

\(2.\)定义完全匹配函数

\(3.\)快速计算每一位的完全匹配函数值

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define debug(...) fprintf(stderr,__VA_ARGS__)#define Debug(x) cout<<#x<<"="<
         
          <
          
           57){if(c=='-')f=-1;c=getchar();} while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar(); return f*x;}inline char readc(){ register char c=getchar(); while(c==' '||c=='\n'||c=='\t') c=getchar(); return c;}const int MAXN=2e6+5;const double Pi=acos(-1);struct cmpx{ double x,y; inline cmpx(){} inline cmpx(double _x,double _y){x=_x,y=_y;} inline friend cmpx operator + (cmpx a,cmpx b){return cmpx(a.x+b.x,a.y+b.y);} inline friend cmpx operator - (cmpx a,cmpx b){return cmpx(a.x-b.x,a.y-b.y);} inline friend cmpx operator * (cmpx a,cmpx b){return cmpx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);} inline friend cmpx operator * (cmpx a,double b){return cmpx(a.x*b,a.y*b);}}A[MAXN],B[MAXN],C[MAXN];char s[MAXN],t[MAXN];int ans[MAXN],a[MAXN],b[MAXN];int n,m;namespace F_F_T{ int rev[MAXN],limit,l; inline void init(int n){ for(limit=1,l=0;limit<=n;limit<<=1) l++; for(int i=0;i
           
            >1]>>1)|((i&1)<<(l-1)); } inline void FFT(cmpx *A,int type){ for(int i=0;i
            
             =0;i--){ char c=readc(); a[i]=(c!='*')?c-'a'+1:0; } for(int i=0;i