Cod sursa(job #2654331)

Utilizator ardutgamerAndrei Bancila ardutgamer Data 30 septembrie 2020 15:42:46
Problema Potrivirea sirurilor Scor 36
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <fstream>
#include <vector>

using namespace std;

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

const int b1 = 97;
const int MOD = 666013;

string a, b;

vector<int>sol;

int main()
{
	getline(fin, a);
	getline(fin, b);
	int hashA = 0;
	int hashB = 0;
	int put1 = 1;
	int na = a.size();
	int nb = b.size();
	int put = 1;
	for (int i = 0; i < na; i++) {
		hashA = ((hashA * b1) % MOD + a[i]) % MOD;
		put = (put * b1) % MOD;
	}
	for (int i = 0; i < nb; i++)
		hashB = ((hashB * b1) % MOD + b[i]) % MOD;
	int cnt = 0;
	if (hashA == hashB && na == nb) {
		cnt++;
		sol.push_back(1);
	}
	hashB = 0;
	for(int i = 0 ; i < na ; i++)
		hashB = ((hashB * b1) % MOD + b[i]) % MOD;
	for (int i = na; i < nb; i++)
	{
		hashB = ((hashB * b1) % MOD + b[i]) % MOD;
		int value = (put * b[i - na]);
		hashB = ((hashB - value) % MOD + MOD) % MOD;
		if (hashA == hashB)
		{
			cnt++;
			if (cnt <= 1000)
				sol.push_back(i - na + 1);
			else
				break;
		}
	}
	fout << cnt << "\n";
	for (int i = 0; i < sol.size(); i++)
		fout << sol[i] << " ";
	fout << "\n";
	return 0;
}