Cod sursa(job #152059)

Utilizator amadaeusLucian Boca amadaeus Data 8 martie 2008 23:29:31
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <string.h>

#define NX 2000010

char P[ NX ], T[ NX ];
int M, N, pi[ NX ], sol[ NX ];

void cit() {
 	gets( P + 1 ); M = strlen( P + 1 ); // the pattern
	gets( T + 1 ); N = strlen( T + 1 ); // the text
	P[0] = T[0] = 0;
}

void calc_pi() {
	int i, k;

	for( k = pi[0] = -1, i = 1; i <= M; pi[ i++ ] = ++k )
		while( P[ i ] != P[ k+1 ] && k != -1 )
			k = pi[k];
}

void rez() {
	int i, k;
	
	calc_pi();

	for( k = 0, i = 1; i <= N; i++ ) {
		while( T[i] != P[ k+1 ] && k != -1 )
			k = pi[k];
		if( ++k == M )
			sol[ ++sol[0] ] = i - M;
     }
}

void scr() {
	int i, min = 1000 < sol[0] ? 1000 : sol[0];
	
	printf( "%d\n", sol[0] );
	for( i = 1; i <= min; i++ )
		printf( "%d ", sol[i] );
}

int main() {
	freopen( "strmatch.in", "r", stdin );
	freopen( "strmatch.out", "w", stdout );

	cit();
	rez();
	scr();

	return 0;
}