Pagini recente » Cod sursa (job #2320639) | Cod sursa (job #103319) | Cod sursa (job #909249) | Cod sursa (job #2217221) | Cod sursa (job #1850086)
#include<stdio.h>
const int MAXN = 4000003;
FILE *in, *out;
char dega[MAXN];
int z[MAXN], lung;
void afisare(int awp)
{
printf("----------------\nawp cyka blyat: %d\n", awp);
for(int i = 1; i <= lung; i++) {
printf("%d ", z[i]);
}
printf("\n");
}
int main ()
{
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;
lung = i + 1;
fscanf(in, "%s", dega + lung);
while(dega[lung] != 0) {
lung++;
}
dega[0] = '#';
dega[lung + 1] = '-';
//printf("%s", dega);
z[0] = z[1] = 0;
int awp = 1;
for(int i = 2; i <= lung; i++) {
if(z[awp] + awp <= i) {
int j = i;
while(dega[j] == dega[j - i + 1]) {
j++;
}
z[i] = j - i;
awp = i;
} else {
if(i - awp + z[i - awp + 1] < z[awp]) {
z[i] = z[i - awp + 1];
} else {
//z[i] = z[i - awp + 1];
int j = z[awp] + awp - 1;
while(dega[j] == dega[j - i + 1]) {
j++;
}
z[i] = j - i;
awp = i;
}
}
//afisare(awp);
}
int tota = 0;
i = 1;
while(i <= lung) {
if(z[i] == gasitd) {
tota++;
}
i++;
}
fprintf(out, "%d\n", tota);
if(tota > 1000) {
tota = 1000;
}
for(int i = 1; i <= lung && tota > 0; i++) {
if(z[i] >= gasitd) {
tota--;
fprintf(out, "%d ", i - 2 - gasitd);
}
}
fclose(in);
fclose(out);
return 0;
}