Cod sursa(job #342166)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 20 august 2009 18:40:25
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include<stdio.h>
#include<vector>
using namespace std;
const int m=666013;
int n,nr,lung,mod;
char s[10000003];
vector <unsigned int> v[m];
vector <unsigned int> :: iterator p;

vector <unsigned int> :: iterator cautare(unsigned int x)
{
	vector <unsigned int> :: iterator it;
	unsigned int r=x%m;
	for(it=v[r].begin();it!=v[r].end();it++)
		if(x==*it)
			return it;
	return v[r].end();
}

inline void adaugare(unsigned int x)
{
	p=cautare(x);
	if(p==v[x%m].end())
		v[x%m].push_back(x);
}

inline void numara(unsigned int x)
{
	p=cautare(x);
	if(p!=v[x%m].end())
		nr++;
}

void read()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	char a[32];
	int i;
	long int x;
	gets(s+1);
	n=strlen(s+1);
	fgets(a,32,stdin);
	lung=strlen(a)-1;
	x=0;
	for(i=0;i<lung;i++)
		x=x*3+a[i]-'a';
	adaugare(x);
	while(fgets(a,32,stdin))
	{
		x=0;
		for(i=0;i<lung;i++)
			x=x*3+a[i]-'a';
		adaugare(x);
	}
	mod=1;
	for(i=1;i<lung;i++)
		mod=mod*3;
}

inline void make_x(unsigned int &x, unsigned int a)
{
	x=(x%mod)*3+a;
}

void rez()
{
	unsigned int x=0;
	int i;
	for(i=1;i<=lung;i++)
		x=x*3+s[i]-'a';
	numara(x);
	for(i=lung+1;i<=n;i++)
	{
		//make_x(x,s[i]-'a');
		numara(x);
	}
	printf("%d\n",nr);
}

int main()
{
	read();
	rez();
	return 0;
}