Cod sursa(job #167068)

Utilizator ProtomanAndrei Purice Protoman Data 28 martie 2008 22:10:30
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 kb
#include <stdio.h>
#include <string>
#define mx 10000010
#define bz 7777777

using namespace std;

struct nod
{
	long long el;
	nod *ua;
} *l[bz+2];
char s[mx+2];
char str[22];
long long v[4];
long i,j,n,nm,h,nr,ok;
long long x;

void clad(long long x)
{
	nod *p;
	long id=x%bz;
	p=new nod;
	p->el=x;
	p->ua=l[id];
	l[id]=p;
}

int comp(long long x, long ct)
{
	nod *p;
	long id=x%bz;
	p=l[id];
	ok=1;
	if (p)
	{
		/*if ((p->el)==x)
		{
			ok=0;
			nr+=ct;
			break;
		}
		p=p->ua;*/
		nr+=ct;
		ok=0;
	}
	return 0;
}

int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	fgets(s,mx+4,stdin);
	nm=strlen(s)-1;
	while (!feof(stdin)) 
	{
		fgets(str,22,stdin);
		h=strlen(str)-1;
		x=0;
		for (i=0; i<h; i++) 
			x=x*3+str[i]-97;
		comp(x,0);
		if (ok)
			clad(x);
	}
	v[1]=1;
	v[2]=2;
	for (i=0; i<h-1; i++)
		for (j=1; j<3; j++)
			v[j]=v[j]*3;
	x=0;
	for (i=0; i<nm; i++)
	{
		if (i>=h)
			x=x-v[s[i-h]-97];
		x=x*3+s[i]-97;
		if (i>h-2)
			comp(x,1);
	}
	printf("%ld",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}