Cod sursa(job #2297326)

Utilizator flibiaVisanu Cristian flibia Data 5 decembrie 2018 18:45:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
#define MOD1 104053  
#define MOD2 104059
#define P 31

using namespace std;

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

string a, b;
int h1[2000100], h2[2000100], lena, lenb, rs, pw1[2000100], pw2[2000100], hash1, hash2, hsh1, hsh2;
vector <int> sol;

int main() {
	in >> a >> b;
	lena = a.size();
	lenb = b.size();
	pw1[0] = 1;
	pw2[0] = 1;
	for (int i = 1; i <= lenb + 1; i++) {
		pw1[i] = (pw1[i - 1] * P) % MOD1;
		pw2[i] = (pw2[i - 1] * P) % MOD2;
	}
	for (int i = 0; i < lena; i++) {
		hash1 = (hash1 + (int) a[i] * pw1[lena - i - 1]) % MOD1;
		hash2 = (hash2 + (int) a[i] * pw2[lena - i - 1]) % MOD2;
		hsh1 = (hsh1 + (int) b[i] * pw1[lena - i - 1]) % MOD1;
		hsh2 = (hsh2 + (int) b[i] * pw2[lena - i - 1]) % MOD2;
	}
	if (hsh1 == hash1 && hsh2 == hash2)
		sol.push_back(0);
	for (int i = lena; i < lenb; i++) {
		hsh1 = (P * hsh1 - pw1[lena] * (int) b[i - lena] + b[i]) % MOD1;
		hsh2 = (P * hsh2 - pw2[lena] * (int) b[i - lena] + b[i]) % MOD2;
		hsh1 = (hsh1 + MOD1) % MOD1;
		hsh2 = (hsh2 + MOD2) % MOD2;
		if (hsh1 == hash1 && hsh2 == hash2)
			sol.push_back(i - lena + 1);
	}
	out << sol.size() << '\n';
	int cnt = 1;
	for (auto i : sol) 
		if (cnt <= 1000) {
			cnt++;
			out << i << ' ';
		}
	return 0;
}