Cod sursa(job #897335)

Utilizator stay_awake77Cangea Catalina stay_awake77 Data 27 februarie 2013 20:02:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#include <cstring>

#define NMAX 2000010

int N, M, Rez, i, ind;
char A[NMAX], B[NMAX];
int Pi[NMAX];
int Pos[1001];

void prefix()
{
	Pi[1] = ind = 0;
	for( i = 2; i <= N; ++i )
	{
		while( ind && A[ind + 1] != A[i] )
			ind = Pi[ind];
		
		if( A[ind + 1] == A[i] )
			++ind;
		Pi[i] = ind;
	}
}

int main()
{
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);
	
	gets( A + 1 ); N = strlen( A + 1 );
	gets( B + 1 ); M = strlen( B + 1 );
	
	prefix();
	
	ind = 0; Rez = 0;
	for( i = 1; i <= M; ++i )
	{
		while( ind && A[ind + 1] != B[i] )
			ind = Pi[ind];
		
		if( A[ind + 1] == B[i] )
			++ind;
		
		if( ind == N )
		{
			++Rez;
			if( Rez <= 1000 )
				Pos[Rez] = i - N + 1;
		}
	}
	
	printf("%d\n", Rez);
	if( Rez > 1000 )
		Rez = 1000;
	for( i = 1; i <= Rez; ++i )
		printf("%d ", Pos[i] - 1);
	printf("\n");
	
	return 0;
}