Cod sursa(job #2723117)

Utilizator Rares31100Popa Rares Rares31100 Data 13 martie 2021 16:06:26
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("strmatch.in");
ofstream out("strmatch.out");
long long cod[2000000];
long long X = 910757677, Y = 901314429, val = 0, putere = 1;
string a, b;

int main()
{
	in >> a >> b;

	for(int i = 0; i < a.size(); i++)
	{
		val = (val * X + a[i]) % Y;
		putere = (putere * X) % Y;
	}
	
	cod[0] = b[0];
	for(int i = 1; i < b.size(); i++)
		cod[i] = (cod[i-1] * X + b[i]) % Y;

	
	int nrSol = 0;
	queue <int> sol;
	if(cod[a.size()-1] == val)
	{
		nrSol++;
		sol.push(1);
	}
	
	for(int i = a.size(); i < b.size(); i++)
		if((cod[i] - cod[i-a.size()] * putere + Y*Y) % Y == val)
		{
			nrSol++;
			sol.push(i - a.size() + 1);
		}
	
	out << nrSol << '\n';
	
	for(int i = 1; i <= min(nrSol, 1000); i++)
	{
		out << sol.front() << ' ';
		sol.pop();
	}
	
	return 0;
}