Cod sursa(job #3202868)

Utilizator laurentiu.maticaMatica Laurentiu-Andrei laurentiu.matica Data 12 februarie 2024 15:24:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
// #include <iostream>

#include <fstream>
#include <string>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

#define MOD1 100007
#define MOD2 100021
#define PRIM 73

int match[2000001];

int main()
{
	string main, pattern;
	getline(cin, pattern);
	getline(cin, main);
	int nm = main.size();
	int np = pattern.size();
	if (np > nm)
	{
		cout << 0;
		return 0;
	}
	int p1, p2, h1, h2, hp1, hp2;
	p1 = p2 = 1;
	h1 = h2 = hp1 = hp2 = 0;
	for (int i = 0; i < np; i++)
	{
		hp1 = (hp1 * PRIM + pattern[i]) % MOD1;
		hp2 = (hp2 * PRIM + pattern[i]) % MOD2;
		h1 = (h1 * PRIM + main[i]) % MOD1;
		h2 = (h2 * PRIM + main[i]) % MOD2;
		if (i)
		{
			p1 = (p1 * PRIM) % MOD1;
			p2 = (p2 * PRIM) % MOD2;
		}
	}
	int n = 0;
	if (h1 == hp1 && h2 == hp2)
		match[n++] = 0;
	for (int i = 1; i <= nm - np; i++)
	{
		h1 = (((h1 - main[i - 1] * p1) % MOD1 + MOD1) * PRIM + main[i + np - 1]) % MOD1;
		h2 = (((h2 - main[i - 1] * p2) % MOD2 + MOD2) * PRIM + main[i + np - 1]) % MOD2;
		if (h1 == hp1 && h2 == hp2)
			match[n++] = i;
	}
	cout << n << '\n';
	if (n > 1000)
		for (int i = 0; i < 1000; i++)
			cout << match[i] << ' ';
	else
		for (int i = 0; i < n; i++)
			cout << match[i] << ' ';
	return 0;
}