Cod sursa(job #701514)

Utilizator BitOneSAlexandru BitOne Data 1 martie 2012 16:18:01
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>
#define N_MAX 2000011

using namespace std;

int countMatch;
string pattern, s;
int lengthPS[N_MAX];
vector< int > match;

void failureFunction( int M )
{
	int i, j=0;

	for( i=2; i <= M; ++i )
	{
		for( ; pattern[i-1] != pattern[j] && j; j=lengthPS[j] );
		if( pattern[i-1] == pattern[j] )
			++j;
		lengthPS[i]=j;
	}
}
void KMP( int N, int M )
{
	int i, j;

	pattern.push_back( ' ' );
	failureFunction( M );
	
	for( i=j=0; i < N; )
	{
		if( pattern[j] == s[i] )
		{
			++i, ++j;
			if( M == j )
			{
				++countMatch;
				if( countMatch <= 1000 )
					match.push_back( i-M );
			}
		}
		else if( j )
				j=lengthPS[j];
			 else ++i; 
	}
	pattern.erase( pattern.end()-1 );
}
int main()
{
	ifstream in( "strmatch.in" );
	ofstream out( "strmatch.out" );

	getline( in, pattern );
	getline( in, s );

	KMP( s.size(), pattern.size() );
	
	out<<countMatch<<'\n';
	copy( match.begin(), match.end(), ostream_iterator<int>( out, " " ) );
	out<<'\n';

	return EXIT_SUCCESS;
}