Pagini recente » Cod sursa (job #1574618) | Cod sursa (job #2868055) | Cod sursa (job #1861956) | Cod sursa (job #2893619) | Cod sursa (job #580136)
Cod sursa(job #580136)
#include <cstdio>
#include <algorithm>
#include <string.h>
using namespace std;
#define Nmax 2000010
int n, m, nr;
char A[Nmax], B[Nmax];
int pi[Nmax], sol[1010];
void prefix () {
int i, p = 0;
for (i = 2; i <= n; i++) {
while (p && A[p + 1] != A[i]) p = pi[p];
if (A[p + 1] == A[i]) p++;
pi[i] = p;
}
}
void kmp () {
int i, p = 0;
for (i = 1; i <= m; i++) {
while (p && A[p + 1] != B[i]) p = pi[p];
if (A[p + 1] == B[i]) 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);
int i, N = min (1000, nr);
for (i = 1; i <= N; i++)
printf ("%d ", sol[i]);
return 0;
}