Cod sursa(job #2767444)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 6 august 2021 11:22:15
Problema Potrivirea sirurilor Scor 40
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD 20000009
#define hashVal 63
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n1, n2, count = 0, stringA_hashVal, stringB_hashVal = 0;
vector<int> ans;

int getVal(char c) {
	if (c >= 'a' && c <= 'z') {
		return c - 'a' + 1;
	} else if (c >= 'A' && c <= 'Z') {
		return c - 'A' + 27;
	}
	return c - '0' + 53;
}

int main() {
	string s1, s2;
	f >> s2 >> s1;
	n1 = s1.length();
	n2 = s2.length();
	int lastHashFactor = 1;
	for (int i = 1; i < n2; i++)
		lastHashFactor = lastHashFactor * hashVal % MOD;
	if (n1 < n2) {
		g << 0;
		return 0;
	}
	
	
	for (int i = 0; i < n2; i++) {
		int val = getVal(s2[i]);
		stringB_hashVal = (stringB_hashVal * hashVal + val) % MOD;
		//cout << "String b hash val: " << stringB_hashVal << "\n";
	}
	//cout << "\n\n";
	
	for (int i = 0; i < n2; i++) {
		int val = getVal(s1[i]);
		stringA_hashVal = (stringA_hashVal * hashVal + val) % MOD;
	}
	//cout << "String a hash val: " << stringA_hashVal << "\n";
	
	if (stringA_hashVal == stringB_hashVal) {
		count++;
		ans.push_back(0);
	}
	for (int i = n2; i < n1; i++) {
		int prevVal = getVal(s1[i-n2]);
		int val = getVal(s1[i]);
		int newPos = stringA_hashVal % MOD - (prevVal * lastHashFactor) % MOD;
		//cout << "New pos hash val: " << newPos << "\n";
		if (newPos < 0)
			newPos += MOD;
		stringA_hashVal = ((newPos % MOD) * hashVal + val) % MOD;
		//stringA_hashVal = (stringA_hashVal + val) % MOD;
		//cout << "String a hash val: " << stringA_hashVal << "\n";
		if (stringB_hashVal == stringA_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;
}