萌新求助字符串
查看原帖
萌新求助字符串
119986
china·xyc楼主2020/7/24 16:30

不知为啥Wa了最后两个点,换模数也没用。

/*
3 7
a*b
aebr*ob
*/
# include <bits/stdc++.h>
using namespace std;
namespace fastio{
	template<typename tn> void read(tn &a){
	    tn x=0,f=1;char c=' ';
	    for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	    for(;isdigit(c);c=getchar() ) x=x*10+c-'0';
	    a=x*f;
	}
	template<typename tn> void print(tn a){
	    if(a<0) putchar('-'),a=-a;
	    if(a>9) print(a/10);
	    putchar(a%10+'0');
	}
};
#define ll long long
using namespace fastio;
const int N=6e5+5;
int n,m;
const int mod=167772161,g=3;
class Array{
    private:
        vector<int>a;
    public:
        Array(const int size,const int f):a(size,f){}
        void push(int n){a.push_back(n);}
        Array(int* l=NULL,int* r=NULL){while(l!=r)push(*l),++l;}
        inline int size(){return a.size();}
        inline int& operator [] (const int x){return a[x];}
        void resize(int n){a.resize(n);}
        void clear(){a.clear();}
        void swap(){reverse(a.begin(),a.end());}
};
int poww(int a,int b,int mod){
    int ans=1;
    while(b){
    	if(b&1) ans=1ll*ans*a%mod;
    	a=1ll*a*a%mod;
    	b>>=1;
    }
    return ans;
}
int* NTT(const int len,Array& a,const bool Ty,int* r=NULL){
    if(!r){
        r=new int[len];
        r[0]=0;int L=log2(len);
        for(int i=0;i<len;i++)
            r[i]=(r[i>>1]>>1)|((i&1)<<L-1);
    }
    for(int i=0;i<len;i++)
        if(i<r[i])swap(a[i],a[r[i]]);
    for(int i=1;i<len;i<<=1){
        int T=poww(Ty?g:poww(g,mod-2,mod),(mod-1)/(i<<1),mod);
        for(int W=i<<1,j=0;j<len;j+=W){
            ll omega=1;
            for(int k=0;k<i;++k,omega=omega*T%mod){
                ll x(a[j+k]),y(omega*a[i+j+k]%mod);
                a[j+k]=x+y;(a[j+k]>mod)&&(a[j+k]-=mod);
                a[i+j+k]=x-y+mod;(a[i+j+k]>mod)&&(a[i+j+k]-=mod);
            }
        }
    }
    return r;
}
Array Mul(Array x,Array y){
    int n=x.size()-1,m=y.size()-1;
    int limit=1;
    while(limit<=n+m)limit<<=1;
    Array ans;
    x.resize(limit+1);
    y.resize(limit+1);
    int *r;
    r=NTT(limit,x,1);
    NTT(limit,y,1,r);
    for(int i=0;i<=limit;i++) x[i]=1ll*x[i]*y[i]%mod;
    NTT(limit,x,0,r);
    int tem=poww(limit,mod-2,mod);
    for(int i=0;i<=n+m;i++) x[i]=(ll)x[i]*tem%mod;
    x.resize(n+m+1);
    return x;
}
Array a,b;
int main(){
	read(m);read(n);
	for(int i=0;i<m;i++){
		char c=getchar();
		if(c!='*') a.push(c-'a'+1);
		else a.push(0);
	}
	getchar();
	for(int i=0;i<n;i++){
		char c=getchar();
		if(c!='*') b.push(c-'a'+1);
		else b.push(0);
	}
	a.swap();
	a.resize(n);
	Array a1=a;
	for(int i=0;i<a1.size();i++) a1[i]=a1[i]*a1[i]*a1[i];
	Array f1=Mul(a1,b);
	Array b1=b; 
	for(int i=0;i<b1.size();i++) b1[i]=b1[i]*b1[i]*b1[i];
	Array f2=Mul(a,b1);
	Array a2=a,b2=b;
	for(int i=0;i<a2.size();i++) a2[i]=a2[i]*a2[i];
	for(int i=0;i<b2.size();i++) b2[i]=b2[i]*b2[i];
	Array f3=Mul(a2,b2);
	Array f=f1;
	for(int i=0;i<f.size();i++) f[i]=1ll*(f[i]+f2[i])%mod;
	for(int i=0;i<f.size();i++) f[i]=1ll*(f[i]-2ll*f3[i]%mod+mod)%mod;
	int ans=0;
	queue<int> q;
	for(int i=m-1;i<n;i++) if(f[i]==0) ans++,q.push(i-m+2);
	printf("%d\n",ans);
	while(q.size()){
		printf("%d ",q.front());
		q.pop();
	}
	return 0;
}
2020/7/24 16:30
加载中...