Cod sursa(job #754413)

Utilizator alexeiIacob Radu alexei Data 2 iunie 2012 00:08:53
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.24 kb
#include<string>
#include<vector>
#include<fstream>
#include<algorithm>

using namespace std;

#define NMAX 20000200

void compute_prefix( string& P , vector< int >& prefix)
{
	int sz = P.size();
	prefix.resize( sz + 1 );

	prefix[0] = 0;
	
	int i , k = 0;
	for( i = 1; i < sz; ++i )
	{
		while( k > 0 && P[k] != P[i] )
			k = prefix[k];

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

		prefix[i] = k;
	}
}

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

	string P, S;
	
	getline(f,P);
	getline(f,S);

	int sz = S.size(), p_sz = P.size();
	P.resize( p_sz + 1 );

	vector< int > prefix;
	compute_prefix( P , prefix );

	int ans[1024], ans_count = 0;

	int i, matched = 0;
	for( i = 0; i < S.size(); ++i )
	{
		while( matched > 0 && P[ matched ]  != S[i] )
			matched = prefix[ matched -1 ];

		if( P[ matched ] == S[i] )
			++matched;
		
		if( matched == p_sz )
		{	
			if( ans_count < 1001 )
				ans[ ans_count ] = i - p_sz + 1;

			++ans_count;
		}
	}

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

	return 0;
}