Cod sursa(job #167040)

Utilizator ProtomanAndrei Purice Protoman Data 28 martie 2008 21:20:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <stdio.h>
#include <string>
#define mx 10000010

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,ax,bz;

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;
	while (p)
	{
		if ((p->el)==x)
		{
			ok=0;
			nr+=ct;
			break;
		}
		p=p->ua;
	}
	return 0;
}

int main()
{
	bz=184371
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	fgets(s+1,mx+4,stdin);
	nm=strlen(s+1)-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]-96;
		comp(x,0);
		if (ok)
			clad(x);
	}
	v[1]=1;
	for (i=0; i<h; i++)
		v[1]=v[1]*3;
	v[2]=v[1]*2;
	v[3]=v[1]*3;
	x=0;
	for (i=1; i<=nm; i++)
	{
		ax=s[i]-96;
		x=x*3+ax;
		x=x-v[s[i-h]-96];
		if (i>h-1)
			comp(x,1);
	}
	printf("%ld",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}