Cod sursa(job #2582193)

Utilizator radustn92Radu Stancu radustn92 Data 16 martie 2020 14:43:49
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
string pattern, text;

const int P = 73;
const int MOD1 = 1e9+9;
const int MOD2 = 1e9+21;
const int NMAX = 2000505;

long long P_POW_MOD1[NMAX], P_POW_MOD2[NMAX], H_MOD1[NMAX], H_MOD2[NMAX];

int main() {
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> pattern >> text;
	P_POW_MOD1[0] = P_POW_MOD2[0] = 1;
	for (int exp = 1; exp < NMAX; exp++) {
		P_POW_MOD1[exp] = (P_POW_MOD1[exp - 1] * P) % MOD1;
		P_POW_MOD2[exp] = (P_POW_MOD2[exp - 1] * P) % MOD2;
	}
	int N = (int) pattern.size(), M = (int) text.size();

	long long hashMod1 = 0L, hashMod2 = 0L;
	for (int idx = 0; idx < N; idx++) {
		hashMod1 = (hashMod1 + P_POW_MOD1[idx] * (pattern[idx] - 'A' + 1)) % MOD1;
		hashMod2 = (hashMod2 + P_POW_MOD2[idx] * (pattern[idx] - 'A' + 1)) % MOD2;
	}

	for (int idx = 0; idx < M; idx++) {
		H_MOD1[idx + 1] = (H_MOD1[idx] + P_POW_MOD1[idx] * (text[idx] - 'A' + 1)) % MOD1;
		H_MOD2[idx + 1] = (H_MOD2[idx] + P_POW_MOD2[idx] * (text[idx] - 'A' + 1)) % MOD2;
	}

	int matches = 0;
	vector<int> sol;
	for (int st = 1; st <= M - N; st++) {
		long long currH_MOD1 = (H_MOD1[st + N - 1] + MOD1 - H_MOD1[st - 1]) % MOD1;
		long long currH_MOD2 = (H_MOD2[st + N - 1] + MOD2 - H_MOD2[st - 1]) % MOD2;
		if ((hashMod1 * P_POW_MOD1[st - 1]) % MOD1 == currH_MOD1 &&
			(hashMod2 * P_POW_MOD2[st - 1]) % MOD2 == currH_MOD2) {
			matches++;
			if (matches <= 1000) {
				sol.push_back(st);
			}
		}
	}

	cout << matches << "\n";
	for (auto match : sol) {
		cout << match - 1 << " ";
	}
	cout << "\n";
	return 0;
}