Pagini recente » Cod sursa (job #712878) | Cod sursa (job #1133926) | Cod sursa (job #1641830) | Cod sursa (job #2613114) | Cod sursa (job #1446414)
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define _submit
#ifdef _submit
#define InFile "strmatch.in"
#define OutFile "strmatch.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif
#define MAXLEN 2010000
#define MAXDLEN 4010000
char strpat[MAXDLEN], *str, *pat;
int strpatlen, slen, patlen;
int F[MAXDLEN];
char matched[MAXLEN];
int mnr = 0;
void buildFail() {
F[0] = -1;
for (int i = 1; i <= strpatlen; i++) {
int k = F[i - 1];
while ((k != -1) && (strpat[i - 1] != strpat[k]))
k = F[k];
F[i] = k + 1;
}
}
void buildZ() {
for (int i = patlen; i < slen + patlen; i++)
if (i - F[i] >= patlen && F[i] >= patlen) {
mnr++;
matched[i - F[i] - patlen] = 1;
}
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OutFile, "w", stdout));
pat = strpat;
scanf("%s", pat);
patlen = strlen(pat);
str = strpat + patlen;
scanf("%s", str);
slen = strlen(str);
strpatlen = patlen + slen;
buildFail();
buildZ();
int printed = 0;
printf("%d\n", mnr);
for (int i = 0; i < slen && printed < 1000; i++)
if (matched[i]) {
printed++;
printf("%d ", i);
}
printf("\n");
return 0;
}