Pagini recente » Autentificare | Cod sursa (job #3345894) | Cod sursa (job #388002)
Cod sursa(job #388002)
#include <cstdio>
#include <string.h>
#define Nmax 2000010
char a[Nmax], b[Nmax];
int A, B;
int sol[1024], N, pi[Nmax];
void prefix () {
int p = 0, i;
for (i = 2; i <= A; i++) {
while (p && a[p + 1] != a[i])
p = pi[p];
if (a[p + 1] == a[i])
pi[i] = ++p;
}
}
void kmp () {
int p = 0, i;
for (i = 1; i <= B; i++) {
while (p && b[i] != a[p + 1])
p = pi[p];
if (a[p + 1] == b[i]) {
p++;
if (p == A) {
N++;
if (N <= 1000) sol[N] = i - A;
}
}
}
}
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
a[0] = b[0] = ' ';
scanf ("%s", a + 1); scanf ("%s", b + 1);
A = strlen (a) - 1; B = strlen (b) - 1;
prefix ();
kmp ();
printf ("%d\n", N);
if (N > 1000) N = 1000;
for (int i = 1; i <= N; i++)
printf ("%d ", sol[i]);
return 0;
}