Cod sursa(job #98201)

Utilizator webspiderDumitru Bogdan webspider Data 10 noiembrie 2007 11:04:55
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 1.41 kb
#include <iostream>
#include <stdio.h>

using namespace std;

const int maxL = 21;
const int maxS = 1000001;
const int maxT = 10000002;

const int A = 0;
const int B = 1;
const int C = 2;

int stareCur;
int nrStari;
int nPoz;
int m;
char text[ maxT ];
char auxc[ maxL ];
int stare[ maxS ][ 3 ];
bool pf[ maxS ];

int ret( char lt ) {
	if ( lt == 'a' ) return 0;
	if ( lt == 'b' ) return 1;
	if ( lt == 'c' ) return 2;
}

void make_automat( char *cuv ) {
	int n = strlen( cuv );
	int i,j;
	int temp;
	stareCur = 0;
	for ( i = 0; i < n; i++ ) {
		if ( stare[ stareCur ][ ret( cuv[i] ) ] <= stareCur ) {
			nrStari++;
			temp = stare[ stareCur ][ ret( cuv[i] ) ];
			stare[ stareCur ][ ret( cuv[i] ) ] = nrStari;
			for ( j = 0; j < 3; j++ )
				stare[ nrStari ][ j ] = stare[ temp ][ j ];
			if ( i == n-1 )
				pf[ nrStari ] = 1;
			stareCur = nrStari;
		}
		else stareCur = stare[ stareCur ][ ret(cuv[i]) ];
	}
}

int main() 
{
	int i;

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

	scanf("%s\n", text);
	while ( !feof( stdin ) ) {
		scanf("%s\n", auxc );
		make_automat( auxc );
	}
	/* Debug
	for ( i = 0; i <= nrStari; i++ )
		printf("%d %d %d\n", stare[ i ][0], stare[ i ][1], stare[ i ][2] );
	*/
	stareCur = 0;
	m = strlen( text );
	for ( i = 0; i < m; i++ ) {
		stareCur = stare[ stareCur ][ ret( text[i] ) ];
		if ( pf[ stareCur ] ) 
			nPoz++;
	}
	printf("%d\n", nPoz );

	fclose(stdin);
	fclose(stdout);

	return 0;
}