Cod sursa(job #166789)

Utilizator ProtomanAndrei Purice Protoman Data 28 martie 2008 14:49:53
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#include <string>
#define mx 10000010
#define bz 194437

using namespace std;

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

void clad(long t)
{
	nod *p;
	p=new nod;
	strcpy(p->el+1,str+1);
	p->ua=l[t];
	l[t]=p;
}

int comp(long x)
{
	long i;
	nod *p;
	p=l[x];
	int ok=0;
	while (p)
	{
		for (i=1; i<=h; i++)
			if ((p->el)[i]!=str[i])
				break;
		if (i==h+1)
		{
			ok=1;
			break;
		}
		p=p->ua;
	}
	return ok;
}

int main()
{
	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+1,25,stdin);
		h=strlen(str+1)-1;
		x=0;
		for (i=1; i<=h; i++) 
			x=(x*3+str[i]-96)%bz;
		if (comp(x)==0)
			clad(x);
	}
	v[1]=1;
	for (i=1; i<=h; i++)
		v[1]=v[1]*3%bz;
	v[2]=v[1]*2%bz;
	v[3]=v[1]*3%bz;
	v[1]=v[1]%bz;
	x=0;
	for (i=1; i<=h; i++)
	{
		x=(x*3+s[i]-96)%bz;
		str[i]=s[i];
	}
	if (comp(x))
		nr++;
	for (i=h+1; i<=nm; i++)
	{
		strcpy(str+1,str+2);
		str[h]=s[i];
		x=(x*3+s[i]-96)%bz;
		x=(x-v[s[i-h]-96]);
		if (x<0)
			x=x+bz;
		if (comp(x))
			nr++;
	}
	printf("%ld",nr);
	fclose(stdin);
	fclose(stdout);
	return 0;
}