Cod sursa(job #100905)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 noiembrie 2007 20:28:59
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.58 kb
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

#define maxl 1024*1024*10
#define prim 10939197
#define prim2 10939197

long n,cat = 0;
char text[maxl];
char pr[prim];
long long s[50001];

void baga(char *sir )
{
	++cat;
	
	for(long i = 0; i < n; ++i)
		s[cat] = s[cat]*3 + sir[i]-'a';
	
}
int strcmpa(const void *a, const void *b)
{
	return *(long *) a - * ( long *)b;
}

int gas(long long a)
{
	long st = 1;
	long dr = cat;
	long mij;
	while( st != dr)
	{
		mij = (st+dr)>>1;
		//if( s[mij] == a) return 1;
		if( s[mij] < a) 
			st = mij+1;
		else dr = mij;
	}
	if( s[st] == a) return 1;
	return 0;
}
void baga2(char *a)
{
	long long w=0;
	for( long i = 0; i < n  ; ++i)
	{
		w = w*3 + a[i]-'a';
	}
	pr[w%prim] = 1;
	
}

int gas2(long a)
{
	return pr[a];
}


int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);

	char sir[32];
	scanf("%s",text);
	
	long ok = 0;
	while( scanf("%s",sir) == 1)
	{
		if( !ok)
			n = strlen(sir);
	
		baga2(sir);
		ok = 1;
	}
	qsort(s+1,cat,sizeof(s[0]),strcmpa);
	
	long long w = 0, p = 1;
	long pp = strlen(text);
	for( long i = 0; i < pp; ++i)
		text[i]-='a';
	
	long rez =0;
	
	for ( long i = 0; i < n-1; ++i)
		p*=3;
	if( n > p)
	{
		printf("0\n");
		return 0;
	}
	for( long i = 0; i < n  ; ++i)
	{
		w = w*3 + text[i];
	}
	
	//return 0;
	
	rez += gas2(w%prim);
	
	long y = w%prim;
	long p2 = p%prim;
	for( long i = n; i < pp; ++i)
	{
		y = ((y- p2 * text[i-n])*3 + text[i])%prim;
		rez+=gas2(y);
	}
	
	printf("%ld\n",rez);
	
	return 0;
}