Cod sursa(job #2938626)

Utilizator RemulseRemulse Remulse Data 12 noiembrie 2022 13:42:39
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string s1, s2;
unsigned long long h1, h2, p_n = 1;
long long p = 31;
vector<int> prez;

int main()
{
	fin >> s1 >> s2;
	if (s1.size() > s2.size())
		swap(s1, s2);
	for (int i = 0; i < s1.size(); i++) {
		h1 = h1 * p + s1[i];
		h2 = h2 * p + s2[i];
		p_n = p_n * p;
	}
	if (h1 == h2)
		prez.push_back(0);
	for (int i = s1.size(); i < s2.size(); i++) {
		h2 = h2 * p + s2[i] - p_n * s2[i - s1.size()];
		if (h1 == h2)
			prez.push_back(i - s1.size() + 1);
	}
	fout << prez.size() << '\n';
	for (int i = 0; i < min(1000, (int)prez.size()); i++) {
		fout << prez[i] << ' ';
	}
}