Cod sursa(job #936243)

Utilizator BitOneSAlexandru BitOne Data 6 aprilie 2013 13:07:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <string>
#include <vector>
#include <fstream>
#include <cstdlib>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;

const int MAXSIZE = 2000011;
const int MAXMATCHES = 1000;

int errorF[MAXSIZE];
vector<int> match;
string pattern, s;

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

void KMP()
{
	int N = s.size(), M = pattern.size(), i, j;
	
	buildErrorF();	
	pattern.push_back(' ');
	for(i = j = 0; i < N; )
	{
		if(pattern[j] == s[i])
		{
			++i, ++j;
			if(M == j)
			{
				match.push_back(i - M);
			}
		}
		else if(j) j = errorF[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();
	out << match.size() << '\n';
	copy(match.begin(), match.begin() + min(MAXMATCHES, match.size()), ostream_iterator<int>(out, " "));
	out << '\n';
}