没有开O2 T了两三个点 有无大佬给科普一下为什么呀...
查看原帖
没有开O2 T了两三个点 有无大佬给科普一下为什么呀...
596291
Qust_yanzhenbin楼主2023/8/1 00:15
#include <bits/stdc++.h>

#define endl '\n'
#define de(x) cout << #x << " = " << x << '\n'
#define dd(x) cout << #x << " = " << x

#define int long long
using namespace std;
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;

const db EPS = 1e-4;
const db PI = acos(-1.);
const int N = 1048576 + 10;	// len = 2^l >= n + m

int res[N], arr1[N], arr2[N];
class Complex {
public:
	double a, b;
	Complex() {}
	Complex(db _a, db _b) : a(_a), b(_b) {}
	
	Complex operator + (const Complex &T) const { return {a + T.a, b + T.b}; }
	Complex operator - (const Complex &T) const { return {a - T.a, b - T.b}; }
	Complex operator * (const Complex &T) const { return {a * T.a - b * T.b, a * T.b + b * T.a}; }
	Complex operator * (const double &n) const { return {a * n, b * n}; }
	Complex operator * (const int &n) const { return {a * n, b * n}; }
	Complex operator / (const db &n) const { return {a / n, b / n}; }
	Complex operator / (const int &n) const { return {a / n, b / n}; }
} A[N], B[N];
//	fft.dft(A, len), fft.dft(B, len); A = A * B (O(n)), fft.idft(A, len)
class FastFourierTransform {
public:
	void dft(Complex y[], int len) { __transform(y, len, 1); }
	void idft(Complex y[], int len) { __transform(y, len, -1); }
private:
	int rev[N];
	void change(Complex y[], int len) {
		for (int i = 0; i < len; ++i, rev[i] = rev[i >> 1] >> 1) if (i & 1) {
			rev[i] |= len >> 1;
		}
		for (int i = 0; i < len; ++i) if (i < rev[i]) {
			 swap(y[i], y[rev[i]]);
		}
		return;
	}
	
	void __transform(Complex y[], int len, int on) {
		change(y, len);
		for (int h = 2; h <= len; h <<= 1) {
			Complex wn(cos(2 * PI / h), sin(on * 2 * PI / h));
			for (int j = 0; j < len; j += h) {
				Complex w(1, 0);
				for (int k = j; k < j + h / 2; k++, w = w * wn) {
					Complex u = y[k], t = w * y[k + h / 2];
					y[k] = u + t, y[k + h / 2] = u - t;
				}
			}
		}
		if (on == -1) for (int i = 0; i < len; i++) y[i].a /= len;
	}
} fft;

void solve() {
	/*...*/
	int m, n;
	cin >> m >> n;
	string s, p;
	cin >> p >> s;
	
	int len = 1;
	while (len <= n + m) len <<= 1;
	
	reverse(p.begin(), p.end());
	for (int i = 0; i < m; i++) arr1[i] = p[i] == '*' ? 0 : p[i] - 'a' + 1;
	for (int i = 0; i < n; i++) arr2[i] = s[i] == '*' ? 0 : s[i] - 'a' + 1;
	
	for (int i = 0; i < m; i++) A[i].a = arr1[i] * arr1[i] * arr1[i];
	for (int i = 0; i < n; i++) B[i].a = arr2[i];
	
	fft.dft(A, len);
	fft.dft(B, len);
	
	for (int i = 0; i < len; i++) A[i] = A[i] * B[i];
	fft.idft(A, len);
	
	for (int i = m - 1; i < n; i++) {
		int x = (int)(A[i].a + 0.5);
		res[i] += x;
	}
	
	for (int i = 0; i < len; i++) {
		A[i].a = A[i].b = 0;
		B[i].a = B[i].b = 0;
		A[i].a = arr1[i];
		B[i].a = arr2[i] * arr2[i] * arr2[i];
	}
	
	fft.dft(A, len);
	fft.dft(B, len);
	
	for (int i = 0; i < len; i++) A[i] = A[i] * B[i];
	fft.idft(A, len);
	for (int i = m - 1; i < n; i++) {
		int x = (int)(A[i].a + 0.5);
		res[i] += x;
	}

	for (int i = 0; i < len; i++) {
		A[i].a = A[i].b = 0;
		B[i].a = B[i].b = 0;
		A[i].a = arr1[i] * arr1[i];
		B[i].a = arr2[i] * arr2[i];
	}
	
	fft.dft(A, len);
	fft.dft(B, len);
	
	for (int i = 0; i < len; i++) A[i] = A[i] * B[i];
	fft.idft(A, len);

	vector<int> ans;
	for (int i = m - 1; i < n; i++) {
		int x = (int)(A[i].a + 0.5);
		res[i] -= x * 2;
		if (res[i] == 0) {
			ans.push_back(i - m + 2);
		}
	}
	
	cout << ans.size() << endl;
	for (auto it : ans) cout << it << ' ';
	cout << endl;
}


signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
	return 0;
}

2023/8/1 00:15
加载中...