Pagini recente » Profil AnDrEwBoY | Cod sursa (job #1530191) | Cod sursa (job #1664089) | Cod sursa (job #2015906) | Cod sursa (job #1446474)
#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++, Z[k]++)
if (patstr[R] != patstr[R - k])
break;
L = k; R--;
}
else {
int kprim = k - L; //+ 1;
int B = R - k + 1;
int C = Z[kprim];
if (C < B)
Z[k] = C;
else {
int A = R - L + 1;
int cpA = A;
for (++R; R < patstrlen; ++R, ++A)
if (patstr[R] != patstr[A])
break;
L = k;
R--;
Z[k] = R - k + cpA;
}
}
}
}
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;
}