Cod sursa(job #2985046)

Utilizator andrei_C1Andrei Chertes andrei_C1 Data 25 februarie 2023 16:31:42
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.72 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 2000000;
const int MOD1 = 1e9 + 7;
const int MOD2 = 1e9 + 9;
const int BASE = 29;

int n, m;
char A[NMAX + 1], B[NMAX + 1];
int powBASE[NMAX + 1];
int nr, v[1001];
int hA1, hB1;
int hA2, hB2;

// n n-1        0
// [------------]
//  [------------]
//  n n-1        0

int main() {
	fin >> A >> B;
	n = strlen(A);
	m = strlen(B);

	if(n > m) {
		fout << "0\n";
		return 0;
	}

	powBASE[0] = 1;
	for(int i = 1; i <= n; i++) {
		powBASE[i] = (long long) powBASE[i - 1] * BASE % MOD1;
	}

	for(int i = 0; i < n; i++) {
		hA1 = (long long) hA1 * BASE % MOD1 + (A[i] - 'A');
		if(hA1 >= MOD1) {
			hA1 -= MOD1;
		}
		hA2 = (long long) hA2 * BASE % MOD2 + (A[i] - 'A');
		if(hA2 >= MOD2) {
			hA2 -= MOD2;
		}
	}

	for(int i = 0; i < n; i++) {
		hB1 = (long long) hB1 * BASE % MOD1 + (B[i] - 'A');
		if(hB1 >= MOD1) {
			hB1 -= MOD1;
		}
		hB2 = (long long) hB2 * BASE % MOD2 + (B[i] - 'A');
		if(hB2 >= MOD2) {
			hB2 -= MOD2;
		}
	}

	if(hA1 == hB1 && hA2 == hB2) {
		nr++;
		v[nr] = 0;
	}

	for(int i = 1; i + n - 1 < m; i++) {
		hB1 -= (long long) (B[i - 1] - 'A') * powBASE[n - 1] % MOD1;
		if(hB1 < 0) {
			hB1 += MOD1;
		}
		hB1 = (long long) hB1 * BASE % MOD1;
		hB1 += (B[i + n - 1] - 'A');
		if(hB1 >= MOD1) {
			hB1 -= MOD1;
		}

		hB2 -= (long long) (B[i - 1] - 'A') * powBASE[n - 1] % MOD2;
		if(hB2 < 0) {
			hB2 += MOD2;
		}
		hB2 = (long long) hB2 * BASE % MOD2;
		hB2 += (B[i + n - 1] - 'A');
		if(hB2 >= MOD2) {
			hB2 -= MOD2;
		}

		if(hA1 == hB1 && hA2 == hB2) {
			nr++;
			if(nr <= 1000) {
				v[nr] = i;
			}
		}
	}

	fout << nr << '\n';
	for(int i = 1; i <= min(nr, 1000); i++) {
		fout << v[i] << " ";
	}
	return 0;
}