快一页红了,心态炸裂,来个大哥救救,TLE一大片,开O2都T了3个点
查看原帖
快一页红了,心态炸裂,来个大哥救救,TLE一大片,开O2都T了3个点
291939
lihuazou楼主2021/10/28 17:04
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
#include<cstdio>

using namespace std;

struct complex {
	double _x;
	double _y;
	complex(double x = 0, double y = 0);
	complex operator+(const complex& comp);
	complex operator-(const complex& comp);
	complex operator*(const complex& comp);
};

complex::complex(double x, double y) {
	_x = x;
	_y = y;
}

complex complex::operator+(const complex& comp) {
	return complex(_x + comp._x, _y + comp._y);
}

complex complex::operator-(const complex& comp) {
	return complex(_x - comp._x, _y - comp._y);
}

complex complex::operator*(const complex& comp) {
	return complex(_x * comp._x - _y * comp._y, _x * comp._y + _y * comp._x);
}

#define re register

const int N = 2e6 + 100;
const double PI = acos(-1);
complex a[N], b[N], ans[N];
int limit = 1;
int rev[N], value1[N], value2[N], out[N];
char str1[N], str2[N];

inline void FFT(complex* comp, int type) {
	for (re int i = 0; i < limit; i++) if (i < rev[i]) swap(comp[i], comp[rev[i]]);
	for (re int mid = 1; mid < limit; mid <<= 1) {
		complex w = complex(cos(PI / mid), type * sin(PI / mid));
		for (re int st = 0, len = mid << 1; st < limit; st += len) {
			complex p = complex(1, 0);
			for (re int index = 0; index < mid; index++, p = p * w) {
				complex x = comp[st + index], y = comp[st + index + mid] * p;
				comp[st + index] = x + y;
				comp[st + index + mid] = x - y;
			}
		}
	}
}


signed main() {
	int m, n;
	scanf("%d %d", &m, &n);
	scanf("%s", str1);
	scanf("%s", str2);
	reverse(str1, str1 + m);
	for (re int i = 0; i < m; i++) value1[i] = (str1[i] == '*') ? 0 : (str1[i] - 'a' + 1);
	for (re int i = 0; i < n; i++) value2[i] = (str2[i] == '*') ? 0 : (str2[i] - 'a' + 1);
	while (limit < (n + m)) limit <<= 1;
	for (re int i = 0; i <= limit; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) ? (limit >> 1) : 0);
	//##########################
	for (re int i = 0; i <= limit; i++) a[i]._x = value1[i] * value1[i] * value1[i], b[i]._x = value2[i];
	for (re int i = 0; i <= limit; i++) a[i]._y = b[i]._y = 0;
	FFT(a, 1);
	FFT(b, 1);
	for (re int i = 0; i <= limit; i++) ans[i] = ans[i] + a[i] * b[i];
	//###########################
	for (re int i = 0; i <= limit; i++) a[i]._x = value1[i], b[i]._x = value2[i] * value2[i] * value2[i];
	for (re int i = 0; i <= limit; i++) a[i]._y = b[i]._y = 0;
	FFT(a, 1);
	FFT(b, 1);
	for (re int i = 0; i <= limit; i++) ans[i] = ans[i] + a[i] * b[i];
	//###########################
	for (re int i = 0; i <= limit; i++) a[i]._x = value1[i] * value1[i], b[i]._x = value2[i] * value2[i];
	for (re int i = 0; i <= limit; i++) a[i]._y = b[i]._y = 0;
	FFT(a, 1);
	FFT(b, 1);
	complex mul = complex(2);
	for (re int i = 0; i <= limit; i++) ans[i] = ans[i] - a[i] * b[i] * mul;
	//##########################
	FFT(ans, -1);
	int cnt = 0;
	for (re int i = m - 1; i < n; i++) if ((int)(ans[i]._x / limit + 0.5) == 0) out[cnt++] = i - m + 2;
	printf("%d\n", cnt);
	for (re int i = 0; i < cnt; i++) printf("%d ", out[i]);
}
2021/10/28 17:04
加载中...