Pagini recente » Cod sursa (job #2097057) | Cod sursa (job #1078274) | Cod sursa (job #2563865) | Cod sursa (job #390311)
Cod sursa(job #390311)
#include <iostream>
using namespace std;
int Urm[2000002], sol[1002];
char T[2000002], P[2000002];
int main() {
FILE *f1=fopen("strmatch.in", "r"), *f2=fopen("strmatch.out", "w");
int i, j, p, q, t, k, nr=0;
char c;
fscanf(f1, "%s", &P);
fscanf(f1, "%c", &c);
fscanf(f1, "%s", &T);
p=strlen(P); t=strlen(T);
//construiesc functia prefix pentru T
Urm[0]=0; k=-1;
for(i=1; i<p; i++) {
while(k>0 && P[i]!=P[k+1]) {
k=Urm[k];
}
if(P[i]==P[k+1]) { k++; }
Urm[i]=k;
}
k=-1;
for(i=0; i<t; i++) {
while(k>0 && T[i]!=P[k+1]) {
k=Urm[k];
}
if(T[i]==P[k+1]) { k++; }
if(k==p-1) {
nr++;
if(nr<=1000) { sol[nr-1]=i-p+1; }
}
}
fprintf(f2, "%d\n", nr);
if(nr>1000) { nr=1000; }
for(i=0; i<nr; i++) {
fprintf(f2, "%d ", sol[i]);
}
fclose(f1); fclose(f2);
return 0;
}