Cod sursa(job #167025)

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

using namespace std;

struct nod
{
	long long el;
	nod *ua;
} *l[bz+1];
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 t,long long xx)
{
	nod *p;
	p=new nod;
	p->el=xx;
	p->ua=l[t];
	l[t]=p;
}

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

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