Pagini recente » Monitorul de evaluare | Cod sursa (job #2363485) | Istoria paginii utilizator/popescu__dorel | Monitorul de evaluare | Cod sursa (job #2905482)
#include <stdio.h>
#include <math.h>
#define NMAX 2000001
#define POZMAX 1001
int rez[POZMAX];
char sira[NMAX];
char sirb[NMAX];
int nra, nrb;
void calcprefix() {
int i, l;
sira[0] = 0;
for (i=1; i<nra; i++) {
l = sira[i-1];
while (l && sira[i]!=sira[l]) {
l = sira[l-1];
}
if (sira[i] == sira[l]) {
sira[i] = l+1;
}
}
}
int main() {
FILE *fin, *fout;
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
char ch;
int i, j, nra, nrb, nr;
nra = 0;
ch = fgetc(fin);
while (ch!='\n') {
sira[nra] = ch;
nra++;
ch = fgetc(fin);
}
nrb = 0;
ch = fgetc(fin);
while (ch!='\n' && ch!=EOF) {
sirb[nrb] = ch;
nrb++;
ch = fgetc(fin);
}
calcprefix();
i=0;
j=0;
nr = 0;
while (i < nrb) {
if (sirb[i] == sira[j]) {
i++;
j++;
if (j == nra) {
if (nr < 1000) {
rez[nr] = i-j;
}
nr++;
j = sira[j-1];
}
} else {
if (j>0) {
j = sira[j-1];
} else {
i++;
}
}
}
fprintf(fout, "%d\n", nr);
if (nr>=POZMAX) {
nr = 1000;
}
for (i=0; i<nr; i++) {
fprintf(fout, "%d ", rez[i]);
}
fclose(fin);
fclose(fout);
return 0;
}