Cod sursa(job #2566150)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 2 martie 2020 19:09:56
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.3 kb
#include <iostream>
#include <string>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int mod1 = 666013;
const int mod2 = 777013;
const int p = 27;
int p1=1, p2=1;
int hash1B=0, hash2B=0;
int hash1A=0, hash2A=0;
string a;
string b;

vector<int>sol;

int main()
{
	getline(fin, a);
	getline(fin, b);
	int na = a.size();
	int nb = b.size();
	for (int i = 0; i < na; i++)
	{
		hash1A = ((hash1A * p) % mod1 + (a[i] - 'A')) % mod1;
		hash2A = ((hash2A * p) % mod2 + (a[i] - 'A')) % mod2;
		hash1B = ((hash1B * p) % mod1 + (b[i] - 'A')) % mod1;
		hash2B = ((hash2B * p) % mod2 + (b[i] - 'A')) % mod2;
		if (i != 0)
		{
			p1 *= p; p1 %= mod1;
			p2 *= p; p2 %= mod2;
		}
	}
	if (hash1A == hash1B && hash2A == hash2B)
		sol.push_back(1);
	for (int i = na ; i < nb ; i++)
	{
		hash1B = ((((hash1B - (b[i - na] - 'A') * p1 + mod1) % mod1) * p) % mod1 + (b[i] - 'A')) % mod1;
		hash2B = ((((hash2B - (b[i - na] - 'A') * p2 + mod2) % mod2) * p) % mod2 + (b[i] - 'A')) % mod2;
		if (hash1A == hash1B && hash2A == hash2B)
			sol.push_back(i - na + 1);
	}
	fout << sol.size() << "\n";
	int mi = min(1000, (int)sol.size());
	for (int i = 0; i < mi; i++)
		fout << sol[i] << " ";
	return 0;
}