Cod sursa(job #921492)

Utilizator MciprianMMciprianM MciprianM Data 21 martie 2013 00:41:29
Problema Potrivirea sirurilor Scor 18
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <string>
#include <vector>

using namespace std;

static const int MAXN = 2000009;
int prefix[MAXN];
char T[MAXN], P[MAXN];
vector<int> ans;
int total = 0;

void comp_prefix() {
	int k = prefix[0] = 0;
	for(int i = 1; P[i]; i++) {
		while(k > 0 && P[i] != P[k - 1])	k = prefix[k - 1];
		if(P[k] == P[i])	k++;
		prefix[i] = k;
	}
}

void potriveste() {
	for(int i = 0, k = 0; T[i]; i++) {
		while(k > 0 && P[k] != T[i])	k = prefix[k - 1];
		if(P[k] == T[i])	k++;
		if(!P[k]) {
			total++;
			if(total < 1000)	ans.push_back(i - k + 1);
		}
	}
}

int main() {
	ifstream f("strmatch.in");
	f >> P >> T;
	f.close();
	comp_prefix();
	potriveste();
	ofstream g("strmatch.out");
	g << total << endl;
	for(int i = 0; i < ans.size(); i++) {
		g << ans[i] << endl;
	}
	g.close();
	return 0;
}