Cod sursa(job #2723482)

Utilizator Rares31100Popa Rares Rares31100 Data 14 martie 2021 11:19:32
Problema Potrivirea sirurilor Scor 78
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.81 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("strmatch.in");
ofstream out("strmatch.out");
unsigned long long cod[2000001];
unsigned long long X = 915358133, Y = 974328597, 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;
}