Submission #44125453

---

Source Code Expand

#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
#define gcd(x,y) (__gcd((x),(y)))
#define lcm(x,y) ((x)*(y)/gcd((x),(y)))
#define lg(x,y)  (__lg((x),(y)))
#pragma GCC optimize(2)
using namespace std;
 
namespace FastIO
{
    template<typename T=int> inline T read()
    {
        T s=0,w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        return s*w;
    }
    template<typename T> inline void read(T &s)
    {
        s=0; int w=1; char c=getchar();
        while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
        while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
        s=s*w;
    }
    template<typename T,typename... Args> inline void read(T &x,Args &...args)
    {
        read(x),read(args...);
    }
    template<typename T> inline void write(T x,char ch)
    {
        if(x<0) x=-x,putchar('-');
        static char stk[25]; int top=0;
        do {stk[top++]=x%10+'0',x/=10;} while(x);
        while(top) putchar(stk[--top]);
        putchar(ch);
        return;
    }
}
using namespace FastIO;
 
namespace MTool
{   
    #define TA template<typename T,typename... Args>
    #define TT template<typename T>
    static const int Mod=998244353;
    TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
    TT inline void cmax(T &a,T b) {a=max(a,b);}
    TT inline void cmin(T &a,T b) {a=min(a,b);}
    TA inline void cmax(T &a,T b,Args... args) {a=max({a,b,args...});}
    TA inline void cmin(T &a,T b,Args... args) {a=min({a,b,args...});}
    TT inline void Madd(T &a,T b) {a=a+b>Mod?a+b-Mod:a+b;}
    TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
    TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
    TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
    TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
    TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
    TT inline T Cmul(T a,T b) {return a*b%Mod;}
    TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
    TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
    TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
    TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
    TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
    TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
    TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
    TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
    TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
    TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
    TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
    TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
    #undef TT
    #undef TA
}
using namespace MTool;
 
inline void file()
{
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
    return;
}
 
bool Mbe;
 
namespace LgxTpre
{
    static const int MAX=5000010;
    static const int inf=2147483647;
    static const int INF=4557430888798830399;
    static const int mod=1e9+7;
    static const int bas=131;
    
    int n,m;
    char a[MAX],b[MAX];
    
    namespace FFTmatch
	{
        static const double PI=acos(-1);
        static const double eps=0.5;
        struct Complex
        {
            double x,y;
            Complex(double X=0.0,double Y=0.0):x(X),y(Y) {}
            inline friend Complex operator + (Complex a,Complex b) {return Complex(a.x+b.x,a.y+b.y);}
            inline friend Complex operator - (Complex a,Complex b) {return Complex(a.x-b.x,a.y-b.y);}
            inline friend Complex operator * (Complex a,Complex b) {return Complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
            template<typename T> inline friend Complex operator / (Complex a,T b) {return Complex(a.x/b,a.y/b);}
	    };
	
	    typedef vector<Complex> VC;
	    typedef vector<int> VI;
	    int rev[MAX],revnow;
	    inline int Sup(int n)  {int k=0; while((1<<k)<n) ++k; return k;}
	    inline void Rea(int k) {if(k==revnow) return; rev[0]=0; for(int i=1;i<=(1<<k);++i) rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));}
	
	    inline void DFT(VC &F,int K,int typ)
	    {
	        int N=1<<K;
	        for(int i=0;i<N;++i) if(rev[i]>i) swap(F[i],F[rev[i]]);
	        for(int len=2,l=1;len<=N;len<<=1,l<<=1)
	        {
	            Complex stp(cos(2*PI/len),sin(typ*2*PI/len));
	            for(int st=0;st<N;st+=len)
	            {
	                Complex omega(1,0),U,V;
	                for(int i=0;i<l;++i)
	                    U=F[st+i],V=omega*F[st+i+l],
	                    F[st+i]=U+V,F[st+i+l]=U-V,
	                    omega=omega*stp;
	            }
	        }
	        if(typ==-1) for(int i=0;i<N;++i) F[i]=F[i]/N;
	    }
	    inline VI solve(char *a,char *b)
	    {
	    	auto get=[](char c)->int
	    	{
	    		if(c=='_') return 0;
	    		if(c=='.') return 1;
	    		if(c>='A'&&c<='Z') return c-'A'+2;
	    		return c-'a'+28;
			};
			
			VI A,B,ans; VC F,G,H;
			int n=strlen(a),m=strlen(b),N=n+m-1;
			for(int i=1;i<n;++i) B.eb(1);
			for(int i=0;i<m;++i) B.eb(get(b[i]));
			for(int i=1;i<n;++i) B.eb(1);
			m=B.size(),N=n+m-1;
			for(int i=0;i<n;++i) A.eb(get(a[i]));
	        int K=Sup(N); Rea(K);
	        F.resize(1<<K),G.resize(1<<K),H.resize(1<<K);
	        reverse(A.begin(),A.end());
	        for(int i=n;i<(1<<K);++i) A.eb(0);
	        for(int i=m;i<(1<<K);++i) B.eb(0);
	        for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i]*A[i]*A[i],0),G[i]=Complex(B[i],0);
	        DFT(F,K,1),DFT(G,K,1);
	        for(int i=0;i<(1<<K);++i) H[i]=H[i]+F[i]*G[i];
	        for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i],0),G[i]=Complex(B[i]*B[i]*B[i],0);
	        DFT(F,K,1),DFT(G,K,1);
	        for(int i=0;i<(1<<K);++i) H[i]=H[i]+F[i]*G[i];
	        for(int i=0;i<(1<<K);++i) F[i]=Complex(A[i]*A[i],0),G[i]=Complex(B[i]*B[i],0);
	        DFT(F,K,1),DFT(G,K,1);
	        for(int i=0;i<(1<<K);++i) H[i]=H[i]-F[i]*G[i]*Complex(2,0);
	        DFT(H,K,-1);
	        for(int i=n-1;i<m;++i) if(fabs(H[i].x)<eps) ans.eb(i-n+2);
	        return ans;
	    }
	}
    
    inline void mian()
    {
    	scanf("%lld%lld%s%s",&n,&m,a,b);
    	write(FFTmatch::solve(b,a).size(),'\n');
    	return;
    }
}

bool Med;

signed main()
{
//  file();
    fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
    int Tbe=clock();
    LgxTpre::mian();
    int Ted=clock();
    cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
    return (0-0);
}

Submission Info

Compile Error

./Main.cpp: In function ‘void LgxTpre::mian()’:
./Main.cpp:183:11: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  183 |      scanf("%lld%lld%s%s",&n,&m,a,b);
      |      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result