Cod sursa(job #2794725)

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

using namespace std;

const int P = 'z' + 1;
const int MOD1 = 100007;
const int MOD2 = 100009;
const int 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';
	for (int i = A.size(); i < B.size(); i++)
		B[i] -= 'A';

	int hA1 = 0;
	int hA2 = 0;
	int p1 = 1;
	int 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;
		}
	}

	int hB1 = 0;
	int 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;
}