Cod sursa(job #176949)

Utilizator vladcyb1Vlad Berteanu vladcyb1 Data 11 aprilie 2008 23:54:23
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <string.h>

#define MIN( a, b ) ( (a) < (b) ) ? (a) : (b)
#define NMAX 2000001
#define SOLMAX 1001
#define FIN "strmatch.in"
#define FOUT "strmatch.out"

int PI[NMAX];
char A[NMAX], B[NMAX];
int SOL[SOLMAX];
int N, M, nr;
FILE * fin, * fout;

void build_PI()
{
	int i, k = 0;
	
	PI[1] = 0;
	for( i = 2; i <= N; i++ )
	{
		while( A[i] != A[k+1] && k > 0 ) k = PI[k];
		if( A[i] == A[k+1]) k++;
		PI[i] = k;
	}
}

void KMP()
{
	int i, k = 0;
	
	for( i = 1; i <= M; i++ )
	{
		while( B[i] != A[k+1] && k > 0 ) k = PI[k];
		if( B[i] == A[k+1] ) k++;
		if( k == N )
		{
			nr++;
			if ( nr <= 1000 ) SOL[nr] = i - N;
			k = PI[k];
		}
	}
}

int main()
{
	fin = fopen( FIN, "r" );
	fout = fopen( FOUT, "w" );
	fscanf( fin, "%s\n", A+1 );
	fscanf( fin, "%s\n", B + 1 );
	N = strlen( A + 1 );
	M = strlen( B + 1 );
	build_PI();
	KMP();
	fprintf( fout, "%d\n", nr );
	int t = MIN( nr, 1000 );
	for( int i = 1; i <= t; i++ )
		fprintf( fout, "%d ", SOL[i] );
	fprintf( fout, "\n");

	return 0;
}