Cod sursa(job #118705)

Utilizator coderninuHasna Robert coderninu Data 27 decembrie 2007 17:07:03
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Lmax 10000001
#define d 3
#define q 14343517

struct nod { char s[21]; struct nod * urm; };
typedef nod * list;

char T[Lmax], P[21];
long long i, j, N, n, m, h, t, rez, p;
list H[q+1], pp;


int egal(char *A, char *B, long c)
{
	for (int i=0; i<m; i++)
		if (A[i]!=B[i+c]) return 0;
	return 1;
}


int main()
{
	freopen("abc2.in", "r", stdin);
	scanf("%s\n", &T);
	while (!feof(stdin))
	{
		scanf("%s\n", &P);
		if (!m) m=strlen(P);
		for (p=i=0; i<m; i++) p=(p*d+P[i]-'a'+1)%q;
		if (!H[p])
		{
			H[p]=new nod;
			H[p]->urm=NULL;
			memcpy(H[p]->s,P,m);
		}
		else
		{
			list qq=new nod;
			qq->urm=H[p];
			memcpy(qq->s,P,m);
			H[p]=qq;
		}
	}
	fclose(stdin);
	for (h=i=1; i<m; i++) h=(h*d)%q;
	n=strlen(T);
	for (i=0; i<m; i++) t=(d*t+T[i]-'a'+1)%q;
	for (i=0; i<=n-m; i++)
	{
		for (pp=H[t]; pp; pp=pp->urm)
			if (egal(pp->s,T,i))
			{
				rez++;
				break;
			}
		t=(t+d*q-(T[i]-'a'+1)*h)%q;
		t=(t*d+T[i+m]-'a'+1)%q;
	}
	freopen("abc2.out", "w", stdout);
	printf("%lld", rez);
	fclose(stdout);
	return 0;
}