Cod sursa(job #2794643)

Utilizator IanisBelu Ianis Ianis Data 5 noiembrie 2021 11:24:35
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int P = 80;
const int MOD1 = 100007;
const int MOD2 = 100021;
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;
	}

	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';
	for (int i = 0; i < B.size(); i++)
		if (ap[i])
			g << i << ' ';

	return 0;
}