Pagini recente » Cod sursa (job #2888834) | Produse | Cod sursa (job #1405655) | Cod sursa (job #329690) | Cod sursa (job #189329)
Cod sursa(job #189329)
#include <stdio.h>
#include <string.h>
char A[2000002];
int next[26];
char B[2000002];
int N;
int pos[1000];
int main(int argc, char *argv[])
{
FILE *fi = fopen("strmatch.in", "r");
fscanf(fi, "%s\n", A);
fscanf(fi, "%s\n", B);
fclose(fi);
int la = strlen(A);
int lb = strlen(B);
if (la > lb)
goto down;
/* printf("%s\n", A); */
int i;
/* for (i = 0; i < lb; ++i)
printf("%c ", B[i]);
printf("\n"); */
for (i = 0; i < 26; ++i)
next[i] = la;
for (i = 0; i < la-1; ++i)
next[A[i]-'A'] = la - i - 1;
/* for (i = 0; i < 26; ++i)
printf("%c ", 'A'+i);
printf("\n");
for (i = 0; i < 26; ++i)
printf("%d ", next[i]);
printf("\n"); */
i = la - 1;
while (i < lb) {
/* printf("%d %c\n", i, B[i]); */
int j = 0;
while ((j < la) && (A[la-j-1] == B[i-j]))
++j;
/* printf("j: %d\n", j); */
if (j == la) {
if (N < 1000)
pos[N++] = i-la+1;
else
++N;
}
/* printf("Match at %d.\n", i-la+1); */
i += next[B[i] - 'A'];
}
down:
;
FILE *fo = fopen("strmatch.out", "w");
fprintf(fo, "%d\n", N);
for (i = 0; (i < N) && (i < 1000); ++i)
fprintf(fo, "%d ", pos[i]);
fprintf(fo, "\n");
fclose(fo);
return 0;
}