Cod sursa(job #1837116)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 29 decembrie 2016 00:03:39
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <unordered_map>
#include <stack>
#include <bitset>
#include <cctype>
#include <unordered_set>
#define MOD 40009
#define pb push_back
#define INF 0x3f3f3f3f
#define INFLL (1LL*INF*INF)
#define ll long long
#define NMAX 10000005

using namespace std;

typedef pair<int, int> pii;

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

char s[NMAX],word[25];
vector<int> Hash[MOD];

inline void insertHash(unsigned x) {
    unsigned lista=x%MOD;

    Hash[lista].pb(x);
}

inline bool findHash(unsigned x) {
    unsigned lista=x%MOD;

    for(auto it:Hash[lista])
        if(it==x) return 1;

    return 0;
}

int main() {
	int i,lg;
	unsigned p3;
	ll res=0,val;

	fin>>s;
	while(!fin.eof()) {
		fin>>word;

		lg=val=i=0;
		while(word[i]) {
			val=(val*3+word[i]-'a');
			++i;
			++lg;
		}

		if(!findHash(val)) insertHash(val);
	}

	val=0;
	p3=3;
	for(i=0;i<lg-1;++i) {
		val=(val*3+s[i]-'a');
		p3*=3;
	}

	for(;s[i];++i) {
		val=(val*3+s[i]-'a');
		val%=p3;
		res+=findHash(val);
	}

	fout<<res;

	return 0;
}