Cod sursa(job #100271)

Utilizator marius135Dumitran Adrian Marius marius135 Data 12 noiembrie 2007 00:43:27
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.2 kb
#include<stdio.h>
#include<string.h>
#define maxl 1024*1024*10
#define maxn 1024*1024


char text[maxl],*sf;
long nod[maxn][3], n ,last = 1;

long test(long end)
{
	long rez =0;
	long poz = 1;
	char *unde = text;
	char *unde2 = text;
	
	for( ; sf - unde2 >= n; ++unde2)
	{
		poz = 1;
		unde = unde2;
		while( poz && (unde - unde2 < n) )
		{
			poz = nod[poz][ *unde ];
			++unde;
	
		}
		if(poz) ++ rez;
	}
	
	return rez;
}

void baga(char *sir,long poz,long h)
{
	if( h > n) return;
	if( nod[poz][ sir[0]-'a' ] != 0 )
	{
		baga( sir + 1, nod[poz][sir[0] -'a'], h+1 );
		return ;
	}
	for ( long i = h; i <= n; ++i)
	{
		nod[poz][ sir[i-h]-'a' ] = ++last;
		poz = last;
	}
}

int main()
{
	freopen("abc2.in","r",stdin);
	freopen("abc2.out","w",stdout);
	
	char sir[32];
	scanf("%s",text);
	//for( long i =0 ; i < 10000000; ++i)
		//text[i] = 'a';
	long ok = 0;
	while( scanf("%s",sir) == 1)
	{
		if( !ok)
			n = strlen(sir);
		
		baga(sir,1,1);
		ok = 1;
	}
	
	sf = text + strlen(text);
	long x = strlen(text) - n;
	for( long i = 0; i < n +x ; ++i)
		text[i]-='a';
	long rez = 0;
	//return 0;
	rez+= test(x);
	
	
	printf("%ld\n",rez);
	
	return 0 ; 
}