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