Cod sursa(job #448071)

Utilizator darrenRares Buhai darren Data 2 mai 2010 16:34:36
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include<fstream>
#include<string>
using namespace std;

#define size(x) (int)x.size()

void read();
void write();
void make_prefix();
void doit();

string first, second;
int prefix[200], mx;

int main()
{
	read();
	make_prefix();
	doit();
	write();
	return 0;
}

void read()
{
	ifstream fin( "strmatch.in" );
	fin >> first >> second;
	fin.close();
}

void write()
{
	ofstream fout( "strmatch.out" );
	fout << mx;
	fout.close();
}

void make_prefix()
{
	int aux = 0;
	for ( int i = 1; i < size( second ); ++i )
	{
		while ( aux && second[aux + 1] != second[i] )
			aux = prefix[aux];
		if ( second[aux + 1] == second[i] )
			++aux;
		
		prefix[i] = aux;
	}
}

void doit()
{
	int k = -1;
	for ( int i = 0; i < size( first ); ++i )
	{
		if ( first[i] == second[k + 1] )
			++k;
		else
			if ( k > -1 )
				k = prefix[k];
		
		if ( k == size( second ) - 1 )
		{
			++mx;
			k = prefix[k];
		}
	}
}