Cod sursa(job #345425)

Utilizator ancaaaancaaa ancaaa Data 2 septembrie 2009 22:49:05
Problema Potrivirea sirurilor Scor 4
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <iostream>

using namespace std;

// lungimea maxima a modelului
#define M 2000002

// lungimea maxima a textului
#define N 2000002

// modelul
char *P;

// textul
char *T;

// functia prefix
int PI[M];

// dimensiunea modelului
int m;

// dimensiunea textului
int n;

// numarul de aparitii ale modelului in text
int apar=0;

// vectorul de aparitii ale modelului in text
int aparitii[N];

void calcul_functie_prefix() {
	int k;

	PI[1]=0;
	k=0;
	for (int q=2; q<=m; q++) {
		while (k>0 && P[k+1]!=P[q]) k=PI[k];
		if (P[k+1]==P[q]) 
			k++;
		PI[q]=k;
	}
}

void potrivire_kmp() {
	int q;

	calcul_functie_prefix();
	q=0;
	for (int i=1; i<=n; i++) {
		while (q>0 && T[i]!=P[q+1]) q=PI[q];
		if (P[q+1]==T[i]) q++;
		if (q==m) {
			aparitii[++apar]=i-m;
			q=PI[q];
		}
	}
}

int main() {
	T=new char(N);
	P=new char(M);
	
	freopen("strmatch.in", "r", stdin);
	freopen("strmatch.out", "w", stdout);

	cin>>P;
	cin>>T;

	n=strlen(T);
	m=strlen(P);

	// modelul si textul sa inceapa de la pozitia 1
	for (int i=n; i>0; i--)
		T[i]=T[i-1];
	for (int i=m; i>0; i--)
		P[i]=P[i-1];

	potrivire_kmp();

	cout<<apar<<endl;
	if (apar>1000) apar-=1000;
	for (int i=1; i<=apar; i++)
		cout<<aparitii[i]<<" ";

	return 0;
}