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