95分FFT求调
查看原帖
95分FFT求调
954640
zhengzidu楼主2024/7/22 08:59
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0;
	short f=1;
	char c=getchar();
	while(c>57||c<48){
		if(c==45) f=-1;
		c=getchar();
	}
	while(c<58&&c>47){
		x=(x<<1)+(x<<3)+(c^48);
		c=getchar();
	}
	return x*f;
}
inline void write(int x){
	if(x<0ll) putchar(45),x=~x+1;
	if(x>9ll) write(x/10);
	putchar(x%10|48);
}
const long double pi=acos(-1.0);
int n,m,limit,bit;
//struct fast_fourier_transform_recursion{
//	struct complexs{
//	    double x,y;
//		complexs(double xx=0,double yy=0){
//			x=xx,y=yy;
//		}
//	}f[200001],g[200001];
//	friend complexs operator+(complexs a,complexs b){ 
//		return complexs(a.x+b.x,a.y+b.y);
//	}
//	friend complexs operator-(complexs a,complexs b){ 
//		return complexs(a.x-b.x,a.y-b.y);
//	}
//	friend complexs operator*(complexs a,complexs b){ 
//		return complexs(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
//	}
//	void fft(int limit,complexs *f,int op){
//		if(limit==1){
//			return;
//		}
//		complexs a1[limit>>1|7],a2[limit>>1|7];
//		for(int i=0;i<limit;i+=2){
//			a1[i>>1]=f[i];
//			a2[i>>1]=f[i+1];
//		}
//		fft(limit>>1,a1,op);
//		fft(limit>>1,a2,op);
//		complexs omega=complexs(cos(2.0*pi/limit),op*sin(2.0*pi/limit));
//		complexs w=complexs(1,0);
//		for(int i=0;i<(limit>>1);i++,w=w*omega){
//			f[i]=a1[i]+w*a2[i];
//			f[i+(limit>>1)]=a1[i]-w*a2[i];
//		}
//	}
//	void work(){
//		limit=1;
//		while(limit<=n+m){
//			limit<<=1;
//		}
//		fft(limit,f,1);
//		fft(limit,g,1);
//		for(int i=0;i<limit;i++){
//			f[i]=f[i]*g[i];
//		}
//		fft(limit,f,-1);
//		}
//}fft1;
struct fast_fourier_transform_iteration{
	int rev[2000010];
	struct complexs{
	    long double x,y;
		complexs(long double xx=0,long double yy=0){
			x=xx,y=yy;
		}
	}f[2000010],g[2000010];
	friend complexs operator+(complexs a,complexs b){ 
		return complexs(a.x+b.x,a.y+b.y);
	}
	friend complexs operator-(complexs a,complexs b){ 
		return complexs(a.x-b.x,a.y-b.y);
	}
	friend complexs operator*(complexs a,complexs b){ 
		return complexs(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
	}
	void fft(complexs *f,int limit,long double op){
		for(int i=0;i<limit;i++){
			if(i<rev[i]){
				swap(f[i],f[rev[i]]);
			}
		}
		for(int mid=1;mid<limit;mid<<=1){
			complexs omega(cos(pi/mid),op*sin(pi/mid));
			for(int j=0;j<limit;j+=(mid<<1)){
				complexs w(1,0);
				for(int l=0;l<mid;l++,w=w*omega){
					complexs x=f[l+j];
					complexs y=w*f[l+j+mid];
					f[l+j]=x+y;
					f[l+j+mid]=x-y; 
				}
			}
		}
	}
	void work(){
		limit=1;
		while(limit<=n+m){
			limit<<=1;
			bit++;
		}
		for(int i=0;i<=limit;i++){
			rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
		}
		fft(f,limit,1);
		fft(g,limit,1);
		for(int i=0;i<=limit;i++){
			f[i]=f[i]*g[i];
		}
		fft(f,limit,-1);
	}
}fft2;
//#define mod 998244353
//struct ntt_mod998244353{
//	int rev[400001],inv,f[400001],g[400001];
//	long long qckpow(long long a,long long b){
//		long long sum=1;
//		long long base=a; 
//		while(b!=0){
//			if(b%2==1){
//				sum=(sum*base)%mod; 
//			}
//			base=(base*base)%mod; 
//			b/=2;
//		}
//		return sum;
//	}
//	void ntt(int *f,int op){
//		for(int i=0;i<limit;i++){
//			if(i<rev[i]){
//				swap(f[i],f[rev[i]]);
//			}
//		}
//		for(int mid=1;mid<limit;mid<<=1){
//			int omega=qckpow(op==1?3:332748118,(mod-1)/(mid<<1));
//			for(int j=0;j<limit;j+=(mid<<1)){
//				int w=1;
//				for(int k=0;k<mid;k++,w=(w*omega)%mod){
//					int x=f[j+k];
//					int y=w*f[j+k+mid]%mod;
//					f[j+k]=(x+y)%mod;
//					f[j+k+mid]=(x-y+mod)%mod;
//				}
//			}
//		}
//	}
//	void work(){
//		limit=1;
//		while(limit<=n+m){
//			limit<<=1;
//			++bit;
//		}
//		for(int i=0;i<limit;i++){
//			rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
//		}
//		ntt(f,1);
//		ntt(g,1);
//		for(int i=0;i<limit;i++){
//			f[i]=(f[i]*g[i])%mod;
//		}
//		ntt(f,-1);
//		inv=qckpow(limit,mod-2);
//	}
//}ntt1;
char s[300010],t[300010];
vector<int> ans;
signed main(){
	m=read();
	n=read();
	for(int i=0;i<=m-1;i++){
		cin>>t[i];
		if(t[i]=='*'){
			fft2.g[m-i].x=0;
		}
		else{
			fft2.g[m-i].x=(long double)((long double)1.000/(long double)((long double)10001.000+(long double)(t[i]-'a')));
		}
	}
	for(int i=0;i<=n-1;i++){
		cin>>s[i];
		if(s[i]=='*'){
			fft2.f[i+1].x=0;
		}
		else{
			fft2.f[i+1].x=(10001.0+(long double)(s[i]-'a'));
		}
	}
	limit=1;
	while(limit<=n+m){
		limit<<=1;
		bit++;
	}
	for(int i=0;i<limit;i++){
		fft2.rev[i]=(fft2.rev[i>>1]>>1)|((i&1)<<(bit-1));
	}
	fft2.fft(fft2.f,limit,1);
	fft2.fft(fft2.g,limit,1);
	for(int i=0;i<=limit;i++){
		fft2.f[i]=fft2.f[i]*fft2.g[i];
	}
	fft2.fft(fft2.f,limit,-1);
	for(int i=m+1;i<=n+1;i++){
		fft2.f[i].x/=(long double)limit;
		int res=(int)(fft2.f[i].x+0.5);
		if(abs(fft2.f[i].x-((long double)(res)))<=1e-8){
			ans.push_back(i-m);
		}
	}
    write(ans.size());
    printf("\n");
    for(int i=0;i<ans.size();i++){
    	write(ans[i]);
    	printf(" ");
	}
	return 0;
}

WA on 12

2024/7/22 08:59
加载中...