Cod sursa(job #1133973)

Utilizator harababurelPuscas Sergiu harababurel Data 5 martie 2014 21:16:19
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define nmax 2000005
using namespace std;

int pi[nmax];
vector <int> sol;
string pattern, text;

void buildPi() {
	int i, j;
	pi[0] = pi[1] = 0;
	for(i=2; i<=int(pattern.size()); i++) {
		j = pi[i-1];

		while(1) {
			if(pattern[j] == pattern[i-1]) { pi[i] = j+1; break; }
			if(j == 0) { pi[i] = 0; break; }
			j = pi[j];
		}

	}
}

void kmp() {
	int i=0, j=0; //j in text, i in pattern

	while(1) {
		if(j == text.size()) break;

		if(text[j] == pattern[i]) {
			i++;
			j++;
			if(i == pattern.size() && int(sol.size()) < 1000) sol.push_back(j - pattern.size());
		}
		else if(i > 0) i = pi[i]; //daca pot incerca urmatoarea potrivire, o incerc
		else j++; //daca nu, trec mai departe
	}
}


int main() {
	ifstream f("strmatch.in");
	ofstream g("strmatch.out");

	getline(f, pattern);
	getline(f, text);

	buildPi();
	kmp();

	g<<sol.size()<<"\n";
	for(int i=0; i<sol.size(); i++) g<<sol[i]<<" ";
	g<<"\n";

	return 0;
}