Pagini recente » Cod sursa (job #906776) | Cod sursa (job #1995467) | Cod sursa (job #908802) | Cod sursa (job #2847768) | Cod sursa (job #1446477)
#include <cstdio>
#include <cassert>
#include <algorithm>
#include <cstring>
using namespace std;
//#define _submit
#ifdef _submit
#define InFile "strmatch.in"
#define OutFile "strmatch.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif
#define NRDMAX 400010
#define NRMAX 200010
char patstr[NRDMAX], *pat, *str;
int Z[NRDMAX];
int patlen, slen, patstrlen;
int matches[1000];
int mnr;
void buildZ() {
int L = 0, R = 0;
for (int k = 1; k < patstrlen; k++) {
Z[k] = 0;
if (k > R) {
for (R = k; R < patstrlen; R++)
if (patstr[R] != patstr[R - k])
break;
L = k;
Z[k] = R - L;
R--;
}
else {
int kprim = k - L;
int B = R - k + 1;
int C = Z[kprim];
if (C < B)
Z[k] = C;
else {
L = k;
while (R < patstrlen && patstr[R - L] == patstr[R])
R = R + 1;
Z[k] = R - L;
R = R - 1;
}
}
}
}
int main() {
assert(freopen(InFile, "r", stdin));
assert(freopen(OutFile, "w", stdout));
pat = patstr;
scanf("%s", pat);
patlen = strlen(pat);
str = patstr + patlen;
scanf("%s", str);
slen = strlen(str);
patstrlen = patlen + slen;
buildZ();
mnr = 0;
for (int i = patlen; i < patstrlen; i++)
if (Z[i] >= patlen) {
if (mnr < 1000)
matches[mnr] = i - patlen;
mnr++;
}
printf("%d\n", mnr);
int toPrint = (mnr < 1000) ? mnr : 1000;
for (int i = 0; i < toPrint; i++)
printf("%d ", matches[i]);
return 0;
}