Cod sursa(job #2767708)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 15:07:57
Problema Potrivirea sirurilor Scor 14
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD1 20000009
#define MOD2 20000111
#define hashVal 163
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n1, n2, count = 0, stringA1_hashVal, stringB1_hashVal, stringA2_hashVal, stringB2_hashVal;
vector<int> ans;

int main() {
	string s1, s2;
	f >> s2 >> s1;
	n1 = s1.length();
	n2 = s2.length();
	int hashFactor1 = 1, hashFactor2 = 1;
	
	for (int i = 1; i < n2; i++) {
		hashFactor1 = hashFactor1 * hashVal % MOD1;
		hashFactor2 = hashFactor2 * hashVal % MOD2;
	}
	if (n1 < n2) {
		g << 0;
		return 0;
	}
	
	for (int i = 0; i < n2; i++) {
		int val = s2[i] - '0';
		stringB1_hashVal = (stringB1_hashVal * hashVal + val) % MOD1;
		stringB2_hashVal = (stringB2_hashVal * hashVal + val) % MOD2;
	}
	
	for (int i = 0; i < n2; i++) {
		int val = s1[i] - '0';
		stringA1_hashVal = (stringA1_hashVal * hashVal + val) % MOD1;
		stringA2_hashVal = (stringA2_hashVal * hashVal + val) % MOD2;
	}
	if (stringA2_hashVal == stringB2_hashVal && stringA2_hashVal == stringB2_hashVal) {
		count++;
		ans.push_back(0);
	}
	
	for (int i = n2; i < n1; i++) {
		int prevVal = s1[i-n2] - '0';
		int val = s1[i] - '0';
		int pos1 = (stringA1_hashVal - (prevVal * hashFactor1 % MOD1) + MOD1) % MOD1;
		int pos2 = (stringA2_hashVal - (prevVal * hashFactor2 % MOD2) + MOD2) % MOD2;
		stringA1_hashVal = (pos1 * hashVal + val) % MOD1;
		stringA2_hashVal = (pos2 * hashVal + val) % MOD2;
		
		if (stringA1_hashVal == stringB1_hashVal && stringA2_hashVal == stringB2_hashVal) {
			count++;
			if (count <= 1000)
				ans.push_back(i - n2 + 1);
		}
	}
	
	g << count << "\n";
	for (int i = 0; i < ans.size(); i++)
		g << ans[i] << " ";
	return 0;
}