Cod sursa(job #614383)

Utilizator BitOneSAlexandru BitOne Data 6 octombrie 2011 11:32:35
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <vector>
#include <string>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

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