Cod sursa(job #118622)

Utilizator coderninuHasna Robert coderninu Data 27 decembrie 2007 01:44:48
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <stdio.h>
#include <string.h>
#define Nmax 50001
#define Lmax 10000001


struct nod { char s[21]; long ord; int p; } P[Nmax];
char T[Lmax];
long i, j, N, n, m, q=23345123, d=3, h, t, rez;

void sort(long pp, long qq)
{
	long st=pp, dr=qq;
	nod X=P[st];
	while (st<dr)
	{
		while (st<dr && P[dr].p>=X.p) dr--; P[st]=P[dr];
		while (st<dr && P[st].p<=X.p) st++; P[dr]=P[st];
	}
	P[st]=X;
	if (st-1>pp) sort(pp,st-1);
	if (st+1<qq) sort(st+1,qq);
}

long search(long pp, long qq)
{
	long m=(pp+qq)/2;
	if (P[m].p==t) { for ( ; P[m-1].p==t; m--); return m; }
	else if (m==pp || m==qq) return -1;
	else if (P[m].p<t) return search(m,qq);
	else return search(pp,m);
}

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[(P[++N].ord=N)].s);
	fclose(stdin);
	m=strlen(P[1].s);
	for (h=i=1; i<m; i++) h=(h*d)%q;
	for (i=1; i<=N; i++) for (j=0; j<m; j++) P[i].p=(d*P[i].p+P[i].s[j]-'a'+1)%q;
	sort(1,N);
	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 (j=search(1,N); j>0 && P[j].p==t; j++)
			if (egal(P[j].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("%ld", rez);
	fclose(stdout);
	return 0;
}