Pagini recente » Cod sursa (job #2404588) | Cod sursa (job #1644573) | Cod sursa (job #1900701) | Cod sursa (job #846131) | Cod sursa (job #600613)
Cod sursa(job #600613)
# include <cstdio>
# include <cstring>
const char *FIN = "strmatch.in", *FOU = "strmatch.out";
const int MAX = 2000005;
char A[MAX], B[MAX];
int S[1005], pi[MAX], N, M;
void prefix (void) {
for (int i = 2, k = 0; i <= N; pi[i++] = k) {
for (; k && A[k + 1] != A[i]; k = pi[k]);
if (A[k + 1] == A[i]) ++k;
}
}
int main (void) {
freopen (FIN, "r", stdin);
fgets (A + 1, MAX, stdin), N = strlen (A + 1) - 1;
fgets (B + 1, MAX, stdin), M = strlen (B + 1) - 1;
prefix ();
for (int i = 1, q = 0; i <= M; ++i) {
for (; q && A[q + 1] != B[i]; q = pi[q]);
if (A[q + 1] == B[i]) ++q;
if (q == N) q = pi[N], (++S[0] < 1001 ? S[S[0]] = i - N : 0);
}
freopen (FOU, "w", stdout);
printf ("%d\n", S[0]);
for (int i = 1; i <= S[0] && i <= 1000; ++i)
printf ("%d ", S[i]);
}