Cod sursa(job #3228362)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 7 mai 2024 18:22:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

using ftype = complex<double>;

ftype root(double ang) {
	return ftype(cos(ang), sin(ang));
}

void ntt(vector <ftype> &a, bool rev) {
	int n = a.size();
	auto b = a;
	for(int step = n / 2; step > 0; step /= 2) {
		for(int i = 0; i < n / 2; i += step) {
			ftype wn = root(2 * M_PI * i * (rev ? -1 : 1) / n);
			for(int j = 0; j < step; j++) {
				ftype u = a[2 * i + j], v = wn * a[2 * i + j + step];
				b[i + j] = (u + v);
				b[i + j + n / 2] = (u - v);
			}
		}
		swap(a, b);
	}
	if(rev) {
		for(auto& x: a) {
			x /= n;
		}
	}
}

void fastMult(vector<ftype> &a, vector<ftype> &b) {
	int n = a.size() + b.size();
	int p = 1;
	while(p < n) {
		p *= 2;
	}
	n = p;
	a.resize(n);
	b.resize(n);
	ntt(a, 0);
	ntt(b, 0);
	for(int i = 0; i < n; i++) {
		a[i] *= b[i];
	}
	ntt(a, 1);
}

int main() {
	string p, t;
	fin >> p >> t;
	reverse(p.begin(), p.end());
	int n = p.size(), m = t.size();
	if(n > m) {
		fout << "0\n";
	} else {
		vector<ftype> a(m), b(m);
		int sum1 = 0;
		for(int i = 0; i < n; i++) {
			a[i] = p[i];
			sum1 += p[i] * p[i];
		}
		vector<int> sp(m + 1);
		for(int i = 0; i < m; i++) {
			b[i] = t[i];
			sp[i + 1] = t[i] * t[i] + sp[i];
		}
		fastMult(a, b);
		int cnt = 0;
		vector<int> ans;
		for(int i = n - 1; i < m; i++) {
			int sum2 = sp[i + 1] - sp[i - n + 1];
			if(sum1 - 2 * round(a[i].real()) + sum2 == 0) {
				cnt++;
				if(cnt <= 1000) {
					ans.emplace_back(i - n + 1);
				}
			}
		}
		fout << cnt << '\n';
		for(const auto &it: ans) {
			fout << it << " ";
		}
	}
	return 0;
}