Pagini recente » Cod sursa (job #228649) | Cod sursa (job #800310) | Cod sursa (job #286357) | Cod sursa (job #285774) | Cod sursa (job #249791)
Cod sursa(job #249791)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 2000015
int N, M;
char sir[MAXN], match[MAXN];
int p[MAXN];
int sol[1024], sz;
void read () {
fgets (match, MAXN, stdin);
fgets (sir, MAXN, stdin);
for (; (match[M] >= 'A' && match[M] <= 'Z') || (match[M] >= 'a' && match[M] <= 'z')
|| (match[M] >= '0' && match[M] <= '9'); ++M);
for (; (sir[N] >= 'A' && sir[N] <= 'Z') || (sir[N] >= 'a' && sir[N] <= 'z')
|| (sir[N] >= '0' && sir[N] <= '9'); ++N);
}
#define sir (sir - 1)
#define match (match - 1)
void prefix () {
int k = 0;
for (int i = 2; i <= M; ++ i) {
while (k > 0 && match[k + 1] != match[i]) k = p[k];
if (match[k + 1] == match[i]) ++ k;
p[i] = k;
}
}
void KMP () {
int k = 0;
for (int i = 1; i <= N; ++ i) {
while (k > 0 && match[k + 1] != sir[i]) k = p[k];
if (match[k + 1] == sir[i]) ++ k;
if (k == M) {
++ sz;
k = p[M];
if (sz <= 1000)
sol[sz] = i - M;
}
}
}
void solve () {
prefix ();
KMP ();
printf ("%d\n", sz);
for (int i = 1; i <= min(sz, 1000); ++ i) printf ("%d ", sol[i]);
printf ("\n");
}
int main () {
freopen ("strmatch.in", "r", stdin);
freopen ("strmatch.out", "w",stdout);
read ();
solve ();
return 0;
}