Cod sursa(job #119352)

Utilizator coderninuHasna Robert coderninu Data 30 decembrie 2007 19:00:43
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Lmax 10000001
#define d 3
#define q 43517

struct nod {long loc; 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;
short uz[Lmax];


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);
	n=strlen(T);
	scanf("%s\n", &P); m=strlen(P);
	freopen("abc2.in", "r", stdin); scanf("%s\n", &T);
	for (h=i=1; i<m; i++) h=(h*d)%q;
	for (i=0; i<m; i++) t=(t*d+T[i]-'a'+1)%q;
	for (i=0; i<=n-m; i++)
	{
		if (!H[t])
		{
			H[t]=new nod;
			H[t]->urm=NULL;
			H[t]->loc=i;
		}
		else
		{
			list qq=new nod;
			qq->urm=H[t];
			qq->loc=i;
			H[t]=qq;
		}
		t=(t+d*q-(T[i]-'a'+1)*h)%q;
		t=(t*d+T[i+m]-'a'+1)%q;
	}
	while (!feof(stdin))
	{
		scanf("%s\n", &P);
		for (p=i=0; i<m; i++) p=(p*d+P[i]-'a'+1)%q;
		for (pp=H[p]; pp; pp=pp->urm)
			if (!uz[pp->loc] && egal(P,T,pp->loc))
			{
				rez++;
				uz[pp->loc]=1;
			}

	}
	fclose(stdin);
	freopen("abc2.out", "w", stdout);
	printf("%lld", rez);
	fclose(stdout);
	return 0;
}