Pagini recente » Cod sursa (job #3040131) | Monitorul de evaluare | Cod sursa (job #2756876) | Cod sursa (job #1527424) | Cod sursa (job #143706)
Cod sursa(job #143706)
#include <cstdio>
#include <cstring>
const int NMAX = 1 << 21;
const int WMAX = 1000;
char A[NMAX], B[NMAX];
int pi[NMAX], R[WMAX];
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) {
if (NR < WMAX)
R[NR] = i - N + 1;
++NR;
j = pi[j];
}
}
printf("%d\n", NR);
if (NR > WMAX) NR = WMAX;
for (i = 0; i < NR; ++i)
printf("%d ", R[i]);
printf("\n");
return 0;
}