Cod sursa(job #2767739)

Utilizator felix24mihaiPrava Felix Mihai felix24mihai Data 7 august 2021 16:35:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <iostream>
#include <fstream>
#include <vector>
#define MOD1 20000009
#define MOD2 20000111
#define HASH_VAL 63
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n1, n2, count = 0, hashA1, hashB1, hashA2, hashB2;
int hashFactor1 = 1, hashFactor2 = 1;
vector<int> ans;
string s1, s2;
 
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 getHashVal(int index, int prevHashVal, unsigned int hashFunction) {
	int prevVal = getVal(s1[index-n2]), val = getVal(s1[index]), pos;
	if (hashFunction == 0) {
		pos = (prevHashVal - (prevVal * hashFactor1 % MOD1) + MOD1) % MOD1;
		return (pos * HASH_VAL + val) % MOD1;
	}
	pos = (prevHashVal - (prevVal * hashFactor2 % MOD2) + MOD2) % MOD2;
	return (pos * HASH_VAL + val) % MOD2;
}
 
int getFirstHashVal(int length, unsigned int text, unsigned int hashFunction) {
	int ans = 0;
	if (text == 0) {
		for (int i = 0; i < length; i++) {
			int val = getVal(s1[i]);
			ans = (ans * HASH_VAL + val);
			hashFunction == 0 ? ans %= MOD1 : ans %= MOD2;
		}
	} else {
		for (int i = 0; i < length; i++) {
			int val = getVal(s2[i]);
			if (hashFunction == 0) {
				ans = (ans * HASH_VAL + val) % MOD1;
			} else {
				ans = (ans * HASH_VAL + val) % MOD2;
			}
		}
	}
	return ans;
}

void checkHashValues(int hashA1, int hashA2, int hashB1, int hashB2, int index) {
	if (hashA1 == hashB1 && hashA2 == hashB2) {
		count++;
		if (count <= 1000)
			ans.push_back(index - n2 + 1);
	}
}
 
int main() {
	f >> s2 >> s1;
	n1 = s1.length();
	n2 = s2.length();
	if (n1 < n2) {
		g << 0;
		return 0;
	}
	
	for (int i = 1; i < n2; i++) {
		hashFactor1 = hashFactor1 * HASH_VAL % MOD1;
		hashFactor2 = hashFactor2 * HASH_VAL % MOD2;
	}
	
	hashB1 = getFirstHashVal(n2, 1, 0);
	hashB2 = getFirstHashVal(n2, 1, 1);
	hashA1 = getFirstHashVal(n2, 0, 0);
	hashA2 = getFirstHashVal(n2, 0, 1);
	checkHashValues(hashA1, hashA2, hashB1, hashB2, n2 - 1);
	
	for (int i = n2; i < n1; i++) {
		hashA1 = getHashVal(i, hashA1, 0);
		hashA2 = getHashVal(i, hashA2, 1);
		checkHashValues(hashA1, hashA2, hashB1, hashB2, i);
	}
	
	g << count << "\n";
	for (int i = 0; i < ans.size(); i++)
		g << ans[i] << " ";
	return 0;
}