Cod sursa(job #754457)

Utilizator alexeiIacob Radu alexei Data 2 iunie 2012 02:12:55
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<fstream>
#include<string.h>
#include<stdlib.h>
using namespace std;

#define NMAX 2000100

size_t sz = 0, p_sz = 0;
char P[NMAX],S[NMAX];
int* PI;//[NMAX];

void compute_pie()
{
	PI = (int*) calloc ( p_sz , sizeof(int) );

	PI[1] = 0;
	
	size_t i , k = 0;
	for( i = 2; i <= p_sz; ++i )
	{
		while( k && P[k+1] != P[i] )
			k = PI[k];

		if( P[k+1] == P[i] )
			++k;

		PI[i] = k;
	}

}

int main()
{
	fstream f ("strmatch.in",  fstream::in );
	fstream g ("strmatch.out", fstream::out );
	
	//freopen("strmatch.in","r",stdin);
	//freopen("strmatch.out","w",stdout);

	f.getline(P+1,NMAX);
	f.getline(S+1,NMAX);

	//fgets(P,NMAX,stdin);
	//fgets(S,NMAX,stdin);
	
	//p_sz = strlen( P );
	//sz   = strlen( S );
	sz = 1 , p_sz = 1;
	while( P[p_sz] )   ++p_sz;
	while( S[sz] )	   ++sz;

	compute_pie();

	int ans_count = 0, ans[1001];

	size_t i;
	int matched = 0; --p_sz;
	for( i = 1; i <= sz; ++i )
	{
		while( matched > 0 && P[ matched+1 ]  != S[i] )
			matched = PI[ matched ];

		if( P[ matched+1 ] == S[i] )
			++matched;
		
		if( matched == p_sz )
		{	
			matched = PI[ matched ];

			if( ans_count < 1001 )
				ans[ ans_count ] = i - p_sz;

			++ans_count;
		}
	}

	g << ans_count << "\n";
	
	sz = min( ans_count, 1000 );
	for( i = 0; i < sz; ++i )
		g << ans[i] << " ";
	g << "\n";

	return 0;
}