Pagini recente » Cod sursa (job #1077254) | Cod sursa (job #1308878) | Cod sursa (job #839479) | Cod sursa (job #1407838) | Cod sursa (job #345426)
Cod sursa(job #345426)
#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;
apar=1000;
for (int i=1; i<=apar; i++)
cout<<aparitii[i]<<" ";
return 0;
}