Pagini recente » Cod sursa (job #2624477) | Cod sursa (job #1708611) | Cod sursa (job #830316) | Cod sursa (job #2701791) | Cod sursa (job #143704)
Cod sursa(job #143704)
#include <cstdio>
#include <cstring>
const int NMAX = 1 << 21;
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;
}