Cod sursa(job #923603)

Utilizator MciprianMMciprianM MciprianM Data 23 martie 2013 18:14:16
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <cstring>

using namespace std;

static const int MAXN = 2000001, MAXA = 1000;
char T[MAXN], P[MAXN];
int PI[MAXN];
int A[MAXA], kt;

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

int main() {
	int ans = 0, lP, lT, lastP;
	ifstream f("strmatch.in");
	f >> P >> T;
	f.close();
	lP = strlen(P);
	lT = strlen(T);
	lastP = lT - lP + 1;
	pre();
	int k = 0;
	for(int i = 0; T[i]; i++) {
		while(k > 0 && P[k] != T[i])	k = PI[k - 1];
		if(P[k] == T[i])	k++;
		if(!P[k]) {
			if(kt < 1000)	A[kt++] = i - k + 1;
			ans++;
		}
	}
	ofstream g("strmatch.out");
	g << ans << endl;
	for(int i = 0; i < kt; i++) {
		g << A[i] << ' ';
	}
	g << endl;
	g.close();
	return 0;
}