Cod sursa(job #100816)

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


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


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(  (unde - unde2 < n) )
		{
			poz = nod[poz][ *unde ];
			++unde;

		}
		if(poz) ++ rez;
	}

	return rez;
}
long test2(long end)
{
	long rez =0;
	long poz = 1;
	char *unde = text2;
	char *unde2 = text2;
	
	++end;
	for( ; end--; ++unde2)
	{
		poz = 1;
		unde = unde2;
		while(  (unde - unde2 < n - 1) )
		{
			poz = nod2[poz][ *unde ];
			unde+=2;

		}
		if(unde - unde2 <n)
			poz = nod[poz][*unde/3];
		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;
	}
}

void fa()
{
	for( long i = 1; i <= last; ++i)
	{
		for ( long j = 0; j < 9; ++j)
			nod2[i][j] = nod[ nod[i][j/3]][j%3];
	}
}
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);
//	sf2 = text2 + strlen(text);
	long x = strlen(text) - n;
	for( long i = 0; i < n +x ; ++i)
		text[i]-='a';
	for( long i = 0; i < n + x-1; ++i)
	{
		text2[i] = text[i]*3 + text[i+1];
	}
	long rez = 0;
	//return 0;
	fa();
	
	//rez+= test(x);
	rez += test2(x);


	printf("%ld\n",rez);

	return 0 ; 
}