Cod sursa(job #3228359)

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

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

vector<int> add(vector<int> a, const vector<int> &b) {
	a.resize(max(a.size(), b.size()));
	for(int i = 0; i < (int)a.size(); i++) {
		a[i] += i < (int)b.size() ? b[i] : 0;
	}
	return a;
}

vector<int> naiveMult(const vector<int> &a, const vector<int> &b) {
	vector<int> res(2 * max(a.size(), b.size()) - 1);
	for(int i = 0; i < (int)a.size(); i++) {
		for(int j = 0; j < (int)b.size(); j++) {
			res[i + j] += a[i] * b[j];
		}
	}
	return res;
}

vector<int> fastMult(const vector<int> &a, const vector<int> &b) {
	int n = a.size(), m = n / 2;
	if(n <= 32) {
		return naiveMult(a, b);
	}
	vector<int> a0(a.begin(), a.begin() + m), a1(a.begin() + m, a.end());
	vector<int> b0(b.begin(), b.begin() + m), b1(b.begin() + m, b.end());
	vector<int> sumA = add(a0, a1), sumB = add(b0, b1);
	vector<int> a0b0 = fastMult(a0, b0), a1b1 = fastMult(a1, b1), sumMult = fastMult(sumA, sumB);
	vector<int> res(2 * n - 1);
	for(int i = 2 * m; i - 2 * m < (int)a1b1.size(); i++) {
		res[i] += a1b1[i - 2 * m];
	}
	for(int i = m; i - m < (int)sumMult.size(); i++) {
		res[i] += sumMult[i - m];
		res[i] -= i - m < (int)a0b0.size() ? a0b0[i - m] : 0;
		res[i] -= i - m < (int)a1b1.size() ? a1b1[i - m] : 0;
	}
	for(int i = 0; i < (int)a0b0.size(); i++) {
		res[i] += a0b0[i];
	}
	return res;
}

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