Cod sursa(job #806948)

Utilizator BitOneSAlexandru BitOne Data 3 noiembrie 2012 19:28:51
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <string>
#include <vector>
#include <cstdlib>
#include <fstream>
#include <iterator>
#include <algorithm>

using namespace std;

const int NMAX = 2000011;

int countMatches;
int errorF[NMAX];
vector<int> matches;

inline int _min(int x, int y) {return x <= y ? x : y;}
void computeErrorF(string pattern)
{
	int M, i, j;
	
	M = pattern.size();
	for(i = 2, j = 0; i <= M; ++i)
	{
		for(; pattern[i-1] != pattern[j] && j; j = errorF[j]);
		if(pattern[i-1] == pattern[j]) ++j;
		
		errorF[i] = j;
	}
}

void findPattern(string s, string pattern)
{
	int N, M, i, j;
	
	N = s.size();
	M = pattern.size();
	pattern.push_back(' ');
	
	computeErrorF(pattern);
	for(i = j = 0; i < N; )
	{
		if(s[i] == pattern[j])
		{
			++i, ++j;
			
			if(M == j)
			{
				++countMatches;
				if(1000 >= countMatches) matches.push_back(i-M);
			}
		}
		else if(0 != j)
			 {
				j = errorF[j];
			 }
			 else {
					  ++i;
				  }
	}
	
	pattern.erase(pattern.end()-1);
}

int main()
{
	string s, pattern;
	ifstream in("strmatch.in");
	ofstream out("strmatch.out");
	
	getline(in, pattern);
	getline(in, s);
	
	findPattern(s, pattern);
	
	out << countMatches << '\n';
	copy(matches.begin(), matches.end(), ostream_iterator<int>(out, " "));
}