Pagini recente » Cod sursa (job #2353048) | Cod sursa (job #552443)
Cod sursa(job #552443)
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;
#define Nmax 2000010
int n, m, sol;
char A[Nmax], B[Nmax];
int pi[Nmax], Sol[1010];
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 = 0;
for (int i = 1; i <= m; i++) {
while (p && B[i] != A[p + 1]) p = pi[p];
if (A[p+1] == B[i]) p++;
if (p == n) {
sol++;
if (sol <= 1000) Sol[sol] = i - p;
}
}
}
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w", stdout);
A[0] = B[0] = ' ';
scanf ("%s%s", A, B);
n = strlen (A) - 1; m = strlen (B) - 1;
prefix ();
kmp ();
printf ("%d\n", sol);
int N = min (1000, sol);
for (int i = 1; i <= N; i++)
printf ("%d ", Sol[i]);
return 0;
}