Pagini recente » Cod sursa (job #3353933) | Diferente pentru admin/task-ratings-guidelines intre reviziile 29 si 30 | Cod sursa (job #80258) | Cod sursa (job #1361983) | Cod sursa (job #1844701)
#include<stdio.h>
#include<new>
const int MAXN = 4000000;
FILE *in, *out;
char dega[MAXN];
int kmp[MAXN];
int main ()
{
//dega = new char [MAXN];
in = fopen("strmatch.in", "r");
out = fopen("strmatch.out", "w");
fscanf(in, "%s", dega + 1);
int i = 1;
while(dega[i] != 0) {
i++;
}
dega[i] = '@';
int gasitd = i - 1;
int lung = i + 1;
fscanf(in, "%s", dega + lung);
while(dega[lung] != 0) {
lung++;
}
dega[0] = '#';
/*
printf("%d ciuicui\n", gasitd);
for(int i = 0; i <= lung; i++) {
printf("%c ", dega[i]);
}
printf("\n\nmuieba\n");
*/
kmp[1] = 0;
kmp[0] = 0;
for(int i = 2; i <= lung; i++) {
int poz = kmp[i - 1];
while(poz != 0 && dega[i] != dega[poz + 1]) {
poz = kmp[poz];
}
if(poz == 0) {
if(dega[poz + 1] == dega[i]) {
kmp[i] = 1;
} else {
kmp[i] = 0;
}
} else {
kmp[i] = poz + 1;
}
}
/*
for(int i = 0; i <= lung; i++) {
printf("%d ", kmp[i]);
}
printf("\nkmpbabaietebaaaa\n\n");
*/
int tota = 0;
for(int i = 1; i <= lung; i++) {
if(kmp[i] >= gasitd) {
tota++;
}
if(tota >= 1000) {
break;
}
}
fprintf(out, "%d\n", tota);
for(int i = 1; i <= lung && tota > 0; i++) {
if(kmp[i] >= gasitd) {
tota--;
fprintf(out, "%d ", i - 1 - (2 * gasitd));
}
}
fclose(in);
fclose(out);
return 0;
}