Cod sursa(job #177951)

Utilizator amadaeusLucian Boca amadaeus Data 13 aprilie 2008 21:30:17
Problema Potrivirea sirurilor Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <string.h>

#define NX 2000010

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

void cit() {
	P[0] = T[0] = ' ';
	
	fgets( P + 1, NX, stdin );
	lP = strlen( P+1 ) - 1;
	
	fgets( T + 1, NX, stdin );
	lT = strlen( T+1 ) - 1;
}

int i, k;
void rez() {
//	int i, k;
	
	for( pi[0] = k = -1, i = 1; i <= lP; pi[i++] = ++k )
		while( P[i] != P[k+1] && k > -1 )
			k = pi[k];

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

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

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

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

	return 0;
}