Cod sursa(job #1690466)

Utilizator Vasile_RotaruVasea Rotaru Vasile_Rotaru Data 15 aprilie 2016 09:14:14
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<bits/stdc++.h>

using namespace std;

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

#define C 63421

vector<long long>Hash[C];
string s,s1;
int x,p[21],l,l1,i,k;

bool find(long long x)
{
	vector<long long>::iterator b=Hash[x%C].begin(),e=Hash[x%C].end();
	for(;b!=e;++b)
	if(*b=x)return 1;
	return 0;
}

void insert(int x)
{
	if(find(x))return;
	Hash[x%C].push_back(x);
}

int H(string s)
{
	int l=s.length(),sum=0;
	for(i=0;i<l;++i)
	sum=sum+p[i]*(s[i]-'a');
	return sum%C;
}

int main()
{
	ios_base::sync_with_stdio(0);
	fin.tie(0);
	fin>>s;
	l=s.length();
	p[0]=1;
	for(i=1;i<21;++i)p[i]=p[i-1]*5;
	while(fin>>s1)insert(H(s1));
	l1=s1.length();
	int sum=0;
	for(i=0;i<l1;++i)sum=sum+p[i]*(s[i]-'a');
	k+=find(sum);
	for(i=l1;i<l;++i)
	{
		sum=sum/5+p[l1-1]*(s[i]-'a');
		k+=find(sum);
	}
	fout<<k;
	return 0;
}