Cod sursa(job #1413658)

Utilizator BLz0rDospra Cristian BLz0r Data 2 aprilie 2015 00:04:16
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define Nmax 10000002
#define Lmax 22
#define Mod 666013
#define pb push_back

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

vector < unsigned int > Hash[Mod+1];
char s[Nmax], aux[Lmax];
unsigned int p3[22];
int lg, LG;

inline int Number ( char x ){
	return x - 'a';
}

inline unsigned int Key ( unsigned int x ){
	return x % Mod;
}

void InsertValue ( unsigned int x ){
	Hash[Key(x)].pb ( x );
}

bool FindValue ( unsigned int x ){
	vector < unsigned int > :: iterator it;
	
	unsigned int k = Key ( x );
	
	for ( it = Hash[k].begin(); it < Hash[k].end(); ++it )
		if ( *it == x )
			return 1;
	
	return 0;
}

long long GetCode (){
	unsigned int ret = 0;
	
	for ( int i = 0, j = lg; i <= lg; ++i, --j )
		ret = ret + Number ( aux[i] ) * p3[j];
	
	//fprintf ( g, "%d\n", ret );
	
	return ret;
	
}

int main(){
	int rez = 0;
	unsigned int T = 0;
	
	fscanf ( f, "%s%*c", s );
	LG = strlen ( s ) - 1; 
	
	fscanf ( f, "%s%*c", aux );
	lg = strlen ( aux ) - 1;
	
	p3[0] = 1;
	for ( int i = 1; i <= 20; ++i )
		p3[i] = 3 * p3[i-1];
	
	do{
		unsigned int x = GetCode();
		if ( !FindValue ( x ) )
			InsertValue ( x );
		
	}while ( fscanf ( f, "%s%*c", aux ) != EOF );
	
	for ( int i = 0, j = lg ; i <= lg; ++i, --j )
		T = T + 1LL * Number ( s[i] ) * p3[j];
	
	rez += FindValue ( T );
	
	//fprintf ( g, "\n\n%d\n", T );
	
	
	for ( int i = lg + 1, j = 0; i <= LG; ++i, ++j ){
		T = T - 1LL * Number ( s[j] ) * p3[lg];
		T = T * 3 + Number ( s[i] );
		rez += FindValue ( T );
		//fprintf ( g, "%d\n", T );
	}
	
	fprintf ( g, "%d", rez );
	
	return 0;
}