Cod sursa(job #543714)

Utilizator BitOneSAlexandru BitOne Data 28 februarie 2011 15:18:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011


using namespace std;
int F[N_MAX];
int _countMatch;
vector< int > r;
string s, p;
inline void FunctionBuild(void)
{
	int i, j, M=p.size()-1;
	for( i=2; i <= M; ++i )
	{
		for( j=F[i-1]; j && p[j] != p[i-1]; j=F[j] );
		if( p[j] == p[i-1] )
			++j;
		F[i]=j;
	}
}
inline void KMP( void )
{
	int i, j, N=s.size()-1, M=p.size()-1;
	FunctionBuild();
	for( i=j=0; i < N; )
	{
		if( s[i] == p[j] )
		{
			++i, ++j;
			if( M == j )
			{
				++_countMatch;
				if( _countMatch <= 1000 )
					r.push_back(i-M);
			}
		}
		else if( j )
				j=F[j];
			 else ++i; 
	}
}
int main( void )
{
	ifstream in( "strmatch.in" );
	getline( in, p );
	getline( in, s );
	p.push_back(' ');
	s.push_back(' ');
	KMP();
	ofstream out( "strmatch.out" );
	out<<_countMatch<<'\n';
	copy( r.begin(), r.end(), ostream_iterator<int>( out, " " ) );
	out<<'\n';
	return EXIT_SUCCESS;
}