Cod sursa(job #2811752)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 3 decembrie 2021 07:37:16
Problema Abc2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("abc2.in");
ofstream fout("abc2.out");

#pragma GCC optimize("Ofast")

const int base = 3, mod = 30007;
int ans;
string s, t;
vector <unsigned int> d[mod];
int len, len_t;
unsigned int base_pow = 1;

bool check(unsigned int Hash)
{
    unsigned int modh = Hash % mod;
    for(int i = 0; i < d[modh].size(); i++)
        if(d[modh][i] == Hash)
            return true;
    return false;
}

void adauga(string s)
{
	unsigned int myHash = 0;
	for (int i =  0; i < len_t; i++)
		myHash = myHash * base + (s[i] - 'a');
	if (!check(myHash)) {
		unsigned int hmod = myHash % mod;
		d[hmod].push_back(myHash);
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
	fin >> s;
	len = s.length();
	while(fin >> t)
    {
		len_t = t.length();
		adauga(t);
	}

	for(int i = 1; i < len_t; i++)
		base_pow = base_pow * base;

	unsigned int myHash = 0;
	for(int i = 0; i < len_t; i++)
		myHash = myHash * base + (s[i] - 'a');
	if(check(myHash))
		ans++;

	for(int i = len_t; i < len; i++) {
		int prev_val = s[i - len_t] - 'a', val = s[i] - 'a';
		myHash = (myHash - (prev_val * base_pow)) * base + val;
		if(check(myHash))
			ans++;
	}
	fout << ans;
	return 0;
}