开O2WA三个点,求助
查看原帖
开O2WA三个点,求助
87651
www2003楼主2022/4/1 21:20
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
const double eps = 1e-5;
#define N 1205050

struct complex{
	double re,im;
	complex(double a = 0,double b = 0){re = a,im = b;}
}sA[N],sB[N],A[N],B[N],C[N],D[N];

complex operator +(complex a,complex b){return complex(a.re + b.re,a.im + b.im);}
complex operator -(complex a,complex b){return complex(a.re - b.re,a.im - b.im);}
complex operator *(complex a,complex b){return complex(a.re * b.re - a.im * b.im,a.re * b.im + a.im * b.re);}

string a,b;
int n,m;
long long limit;
int l;
int res[N];
int r[N];

double pi = acos(-1);

void FFT(complex *a,long long f)
{
	for(int i = 0; i < limit; i++)
	{
		if(i < r[i])
		{
			swap(a[i],a[r[i]]);
		}
	}
	for(int D = 1; D < limit; D = D * 2)
	{
		complex wn(cos(pi / D), f * sin(pi / D));
		for(int j = 0; j < limit; j += 2 * D)
		{
			complex w(1,0);
			for(int l = 0; l < D; l++)
			{
				complex x = a[j + l];
				complex y = w * a[j + l + D];
				a[j + l] = x + y;
				a[j + l + D] = x - y;
				w = w * wn;	
			}
		}
	}
	if(f == -1)
	{
		for(int i = 0; i < limit; i++)
		{
			a[i].re = (int)(a[i].re / limit + 0.5);
		}
	}
}

void solve1()
{
	limit = 1,l = 0;
	for(int i = 0; i <= m; i++)
	{
		A[i].re = pow(sA[i].re,3);
		B[i].re = sB[i].re;
	}
	//for(int i = 0; i <= m; i++)cout << A[i].re << ' ';cout << endl;
	//for(int i = 0; i <= m; i++)cout << B[i].re << ' ';cout << endl;
	while(limit <= 2 * m)
	{
		limit <<= 1;
		l++;
	} 
	for(int i = 0; i <= limit; i++)r[i] = (r[i >> 1] >> 1) | ((1&i) << (l-1));
	FFT(A,1);FFT(B,1);
	for(int i = 0; i < limit; i++)A[i] = A[i] * B[i];
	FFT(A,-1);
	//for(int i = 0; i <= m + m; i++)cout << A[i].re << ' ';cout << endl;
}
/*
3 5
aaa aabaa
*/

void solve2()
{
	limit = 1,l = 0;
	for(int i = 0; i <= m; i++)
	{
		C[i].re = pow(sA[i].re,2);
		D[i].re = pow(sB[i].re,2);
	}
	while(limit <= 2 * m)
	{
		limit <<= 1;
		l++;
	}
	for(int i = 0; i <= limit; i++)r[i] = (r[i >> 1] >> 1) | ((1&i) << (l-1));
	FFT(C,1); FFT(D,1);
	for(int i = 0; i <= limit; i++)C[i] = C[i] * D[i];
	FFT(C,-1);
	//for(int i = 0; i <= m + m; i++)cout << C[i].re << ' '; cout << endl;
}

void solve3()
{
	limit = 1,l = 0;
	for(int i = 0; i <= m; i++)
	{
		sA[i].re = sA[i].re;
		sB[i].re = pow(sB[i].re,3);
	}
	while(limit <= 2 * m)
	{
		limit <<= 1;
		l++;
	}
	for(int i = 0; i <= limit; i++)r[i] = (r[i >> 1] >> 1) | ((1&i) << (l-1));
	FFT(sA,1); FFT(sB,1);
	for(int i = 0; i <= limit; i++)sA[i] = sA[i] * sB[i];
	FFT(sA,-1); 
	//for(int i = 0; i <= m + m; i++)cout << E[i].re << ' '; cout << endl;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	n--,m--;
	cin >> a >> b;
    if(n > m)
    {
    	cout << 0;
    	return 0;
	}
	for(int i = 0; i <= m; i++)
	{
		if(b[i] == '*')sB[i].re = 0;
		else sB[i].re = b[i] - 'a' + 1;
	}
	for(int i = 0; i <= m; i++)sA[i].re = 0;
	for(int i = 0; i <= n; i++)
	{
		if(a[i] == '*')sA[m - i].re = 0;
		else sA[m - i].re = a[i] - 'a' + 1;
	}
	//for(int i = 0; i <= m; i++)cout << sB[i].re << ' ';
	//for(int i = 0; i <= m; i++)cout << sA[i].re << ' '; 
	//FFT(sA,1);FFT(sB,1);for(int i = 0; i < limit; i++)sA[i] = sA[i] * sB[i]; FFT(sA,-1);
	//for(int i = 0; i <= m + m; i++)cout << sA[i].re << ' '; return 0 ;
	solve1();
	solve2();
	solve3();
	int tp = 0;
	for(int i = m; i <= m * 2 - n; i++)
	{
		double X = A[i].re - 2 * C[i].re + sA[i].re; 
		if(fabs(X) < eps)
		{
			res[++tp] = (i - m + 1);
		}
	}
	cout << tp << endl;
	for(int i = 1; i <= tp; i++)
	{
		cout << res[i] << ' ';
	}
	return 0;
}
2022/4/1 21:20
加载中...