Cod sursa(job #337149)

Utilizator rumburakrumburak rumburak Data 2 august 2009 18:17:21
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include<cstdio>
#include<vector>
#include<cstring>

using namespace std;

const int m = (1<<18);
const int L = (1<<24);
const int masca = m - 1;
const int p = 32452843;

char text[L];

struct nod
{
	long long info;
	nod* adr;
};

nod* h[m];

int k;

long long nr(char *s)
{
	long long r=0;
	for(;*s && *s!='\n';++s)
		r=r*3+(*s-'a');
	return r;
}

bool exista(long long r)
{
	int poz = (r*p)&masca;
	for(nod* i=h[poz] ; i ; i=i->adr)
		if(r==i->info)
			return true;
	return false;
}

inline void adauga(long long r)
{
	int poz=(r*p)&masca;
	nod *aux=new nod;
	aux->info=r;
	aux->adr=h[poz];
	h[poz]=aux;
}

int lung(char *s)
{
	int k=0;
	while(*s && *s!='\n')
	{
		++k;
		++s;
	}
	return k;
}

void citire()
{
	char cuvant[21];
	long long r;
	fgets(text,L,stdin);
	fgets(cuvant,21,stdin);
	r=nr(cuvant);
	k=lung(cuvant);
	adauga(r);
	while(fgets(cuvant,21,stdin))
	{
		r=nr(cuvant);
		if(!exista(r))
			adauga(r);
	}
}

long long pow(int a,int n)
{
	long long p=1;
	while(n--)
		p*=a;
	return p;
}

void calcul()
{
	int rez=0,i;
	long long val=0,mas=pow(3,k-1);
	for(i=0;i<k;++i)
		val=val*3+(text[i]-'a');
	if(exista(val))
		++rez;
	for( ; text[i] && text[i]!='\n' ; ++i)
	{
		val-=(text[i-k]-'a')*mas;
		val=val*3+(text[i]-'a');
		if(exista(val))
			++rez;
	}
	printf("%d\n",rez);
}

int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	citire();
	calcul();
	return 0;
}