Pagini recente » Cod sursa (job #971010) | Cod sursa (job #1799151) | Cod sursa (job #1608746) | Cod sursa (job #2215843) | Cod sursa (job #1444150)
#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
char str[MAXLEN], pat[MAXLEN];
int slen, patlen;
int F[MAXLEN];
int matches[1000];
int mnr = 0;
void buildFail() {
F[0] = -1;
F[1] = 0;
for (int i = 2; i <= patlen; i++) {
if (pat[i - 1] == pat[F[i - 1]])
F[i] = F[i - 1] + 1;
else
F[i] = 0;
}
}
void KMP() {
int m = 0, i = 0;
while (m + i < slen) {
if (i < patlen && str[m + i] == pat[i]) {
if (i == patlen - 1) {
if(mnr < 1000)
matches[mnr] = m;
mnr++;
}
i++;
}
else {
if (i == 0)
m++;
else {
m += i - F[i];
i = F[i];
}
}
}
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OutFile, "w", stdout));
scanf("%s%s", pat, str);
slen = strlen(str);
patlen = strlen(pat);
buildFail();
KMP();
printf("%d\n", mnr);
int nrprint = std::min(mnr, 1000);
for (int i = 0; i < nrprint; i++)
printf("%d ", matches[i]);
printf("\n");
return 0;
}