Pagini recente » Cod sursa (job #1670984) | Cod sursa (job #1406960) | Cod sursa (job #1161358) | Cod sursa (job #89122) | Cod sursa (job #574425)
Cod sursa(job #574425)
#include <cstdio>
#include <cstring>
#define NMAX 2000050
char A[NMAX], B[NMAX];
int V[1024], pi[NMAX], NA, NB, sol, k, i;
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
scanf ("%s\n%s", A + 1, B + 1);
A[0] = ' '; B[0] = ' '; NA = strlen (A)- 1, NB = strlen (B) - 1;
pi[1] = 0;
for (i = 2; i <= NA; i++) {
while (k > 0 && A[i] != A[k + 1])
k = pi[k];
if (A[i] == A[k + 1])
k++;
pi[i] = k;
}
k = 0;
for (i = 1; i <= NB; i++) {
while (k > 0 && B[i] != A[k + 1])
k = pi[k];
if (B[i] == A[k + 1])
k++;
if (k == NA) {
sol++;
if (sol <= 1000) V[sol] = i - NA;
}
}
printf ("%d\n", sol);
if (sol > 1000) sol = 1000;
for (i = 1; i <= sol; i++)
printf ("%d ", V[i]);
return 0;
}