Cod sursa(job #2296784)

Utilizator livliviLivia Magureanu livlivi Data 5 decembrie 2018 00:26:42
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.13 kb
#include <fstream>
#include <unordered_map>
#include <string>
#include <iostream>
#define M ((1 << 20) - 1)
using namespace std;

string s, x;

long long hashtable[M];

bool inside(long long value) {
	int v = value & M;
	while (hashtable[v] != 0) {
		if (hashtable[v] == value) {
			return true;
		}
		v++;
		if (v == M) { v = 0; }
	}
	return false;
}

void insert(long long value) {
	int v = value & M;
	while (hashtable[v] != 0 and hashtable[v] != value) {
		v++;
		if (v == M) { v = 0; }
	}
	hashtable[v] = value;
}

int main(){
	ifstream cin("abc2.in");
	ofstream cout("abc2.out");

	cin >> s;

	while(cin >> x){
		long long cod = 0;
		for(int i = 0; i < x.size(); i++)
			cod = cod * 3 + x[i] - 'a';

		// cout << cod << endl;
		insert(cod + 1);
	}

	int n = x.size();
	long long p3lan = 1;

	for(int i = 1; i < n; i++)
		p3lan *= 3;

	long long cod = 0;
	int ans = 0;
	for(int i = 0, j = 0; i <= s.size() - n; i++){
		while(j < s.size() && j < i + n){
			cod = cod * 3 + s[j] - 'a';
			// cout << cod << endl;
			j++;
		}

		if (inside(cod + 1)) 
			ans ++;

		// cout << cod << endl;
		cod -= p3lan * (s[i] - 'a');
	}

	cout << ans << endl;
	return 0;
}