Pagini recente » Cod sursa (job #266684) | Cod sursa (job #2519440) | Cod sursa (job #659979) | Cod sursa (job #1527431) | Cod sursa (job #143698)
Cod sursa(job #143698)
#include <cstdio>
#include <cstring>
const int NMAX = 1 << 20;
char A[NMAX], B[NMAX];
int pi[NMAX], R[NMAX];
int main(void) {
freopen("strmatch.in", "rt", stdin);
// freopen("strmatch.out", "wt", stdout);
int N, M, NR = 0;
int i, j;
scanf(" %s %s", A, B);
N = strlen(A); M = strlen(B);
pi[0] = pi[1] = 0;
for (i = 1, j = 0; i < N; ++i) {
while (j > 0 && A[i] != A[j]) j = pi[j];
if (A[i] == A[j]) ++j;
pi[i+1] = j;
}
for (i = j = 0; i < M; ++i) {
while (j > 0 && A[j] != B[i]) j = pi[j];
if (A[j] == B[i]) ++j;
if (j == N) {
R[NR++] = i - N + 1;
j = pi[j];
}
}
printf("%d\n", NR);
if (NR > 1000) NR = 1000;
for (i = 0; i < NR; ++i)
printf("%d ", R[i]);
printf("\n");
return 0;
}