Cod sursa(job #2794640)

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

using namespace std;

const int P = 80;
const int MOD = 100007;
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())
		return 0;

	int hA = 0;
	int p = 1;
	for (int i = 0; i < A.size(); i++) {
		hA = (hA * P + A[i]) % MOD;
		if (i != 0)
			p = (p * P) % MOD;
	}

	int hB = 0;
	for (int i = 0; A[i]; i++) {
		hB = (hB * P + B[i]) % MOD;
	}

	if (hA == hB)
		n++;

	for (int i = A.size(); i < B.size(); i++) {
		hB = ((hB - (B[i - A.size()] * p) % MOD + MOD) * P + B[i]) % MOD;

		if (hA == hB) {
			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;
}