Cod sursa(job #527670)

Utilizator mihaipopa12Popa Mihai mihaipopa12 Data 31 ianuarie 2011 23:58:54
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.18 kb
#include<stdio.h>
#include<algorithm>
using namespace std;
#define ui unsigned int

FILE*f=fopen("abc2.in","r");
FILE*g=fopen("abc2.out","w");

int Rez,Lc,i,N,k,step;
ui Nr,W[50005],P;
char C[25],A[10000005];

void transf ( char *C ){
	Nr = 0;
	for ( int i = 1 ; i <= Lc ; ++i ){
		Nr = Nr * 3 + C[i] - 'a' ;
	}
	
}

inline int cautbin ( i64 x ){
	
	int i,stp = step;
	
	for ( i = 0 ; stp ; stp >>= 1 ){
		if ( i + stp < k && W[i + stp] <= x )
			i += stp;
	}
	return W[i] == x ;
	
}

int main () {
	
	fscanf(f,"%s\n",A);
	N = strlen ( A ) - 1;

	fgets(C + 1,25,f);
	for ( i = 1 ; C[i] >= 'a' && C[i] <= 'z' ; ++i ) ;
	Lc = i - 1;
	transf(C); 
	W[++k] = Nr;
	
	while ( fgets( C + 1 , 25 , f ) ){
		transf(C);
		W[++k] = Nr;
	}
	for ( i = 0 ; i < Lc ; ++i )
		C[i + 1] = A[i];
	
	for ( i = 0 , P = 1 ; i < Lc - 1 ; ++i ) P = P * 3;
	
	sort(W+1,W+k+1);
	for (step = 1; step < k ; step <<= 1 );
	
	transf(C);
	if ( cautbin(Nr) )
		++Rez;
	
	for ( i = Lc ; i < N ; ++i ){
		Nr -= ( P * ( A[ i - Lc ] - 'a' ) );
		Nr = Nr * 3 + A[i] - 'a' ;
		
		if ( cautbin(Nr) )
			++Rez;
	}
	
	fprintf(g,"%d",Rez);
	
	fclose(f);
	fclose(g);
	
	return 0;
}