Cod sursa(job #2794734)

Utilizator IanisBelu Ianis Ianis Data 5 noiembrie 2021 12:51:46
Problema Potrivirea sirurilor Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int64_t P = 67;
const int64_t MOD1 = 1e9 + 7;
const int64_t MOD2 = 1e9 + 9;
const int64_t mxN = 2e6+5;

ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A, B;
int n, ap[mxN];

int main() {
	f >> A >> B;
	
	if (A.size() > B.size()) {
		g << 0;
		return 0;
	}

	for (int i = 0; i < A.size(); i++)
		A[i] -= 'A' - 1;
	for (int i = 0; i < B.size(); i++)
		B[i] -= 'A' - 1;

	int64_t hA1 = 0;
	int64_t hA2 = 0;
	int64_t p1 = 1;
	int64_t p2 = 1;
	for (int i = 0; i < A.size(); i++) {
		hA1 = (hA1 * P + A[i]) % MOD1;
		hA2 = (hA2 * P + A[i]) % MOD2;
		if (i != 0) {
			p1 = (p1 * P) % MOD1;
			p2 = (p2 * P) % MOD2;
		}
	}

	int64_t hB1 = 0;
	int64_t hB2 = 0;
	for (int i = 0; A[i]; i++) {
		hB1 = (hB1 * P + B[i]) % MOD1;
		hB2 = (hB2 * P + B[i]) % MOD2;
	}

	if (hA1 == hB1 && hA2 == hB2)
		n++;

	for (int i = A.size(); i < B.size(); i++) {
		hB1 = ((hB1 - (B[i - A.size()] * p1) % MOD1 + MOD1) * P + B[i]) % MOD1;
		hB2 = ((hB2 - (B[i - A.size()] * p2) % MOD2 + MOD2) * P + B[i]) % MOD2;

		if (hA1 == hB1 && hA2 == hB2) {
			ap[i - A.size() + 1] = 1;
			n++;
		}
	}
	g << n << '\n';
	int nr = 0;
	for (int i = 0; i < B.size() && nr < 1000; i++)
		if (ap[i]) {
			g << i << ' ';
			nr++;
		}

	return 0;
}