Cod sursa(job #749489)

Utilizator BitOneSAlexandru BitOne Data 17 mai 2012 14:15:56
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iterator>
#include <algorithm>

using namespace std;

const int N_MAX=2011;
const int MAX=1000;

int main()
{
	string p, s;
	vector<int> match;
	int failureF[N_MAX];
	int pSize, sSize, i, j, countMatch=0;
	
	ifstream in("strmatch.in");
	ofstream out("strmatch.out");
	
	getline(in, p);
	getline(in, s);
	pSize=p.size(), sSize=s.size();
	failureF[0]=failureF[1]=0;
	for(i=2, j=0; i <= pSize; ++i)
	{
		for(; p[i-1] != p[j] && j; j=failureF[j]);
		if(p[i-1] == p[j])
			++j;
		failureF[i]=j;
	}
	p.push_back(' '); s.push_back(' ');	
	for(i=j=0; i < sSize; )
	{
		if(s[i] == p[j])
		{
			++i, ++j;
			if(pSize == j)
			{
				++countMatch;
				if(MAX >= countMatch)
					match.push_back(i-pSize);
			}
		}
		else if(j)
				j=failureF[j];
			 else ++i;
	}
	out<<countMatch<<'\n';
	copy(match.begin(), match.end(), ostream_iterator<int>(out, " "));
	out<<'\n';
	
	return EXIT_SUCCESS;
}