Pagini recente » Cod sursa (job #1415519) | Cod sursa (job #172125) | Cod sursa (job #2827601) | Cod sursa (job #3145301) | Cod sursa (job #2295659)
#include<cstdio>
#include<cstring>
typedef unsigned long long hsh;
#ifdef INFOARENA
#define ProblemName "strmatch"
#endif
#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif
const int MAXN = 2000001;
const int MAXM = 1000;
int m[MAXM], mnr;
char buf[MAXN];
int N, M;
const int B = 29;
int main() {
freopen(InFile, "r", stdin);
freopen(OuFile, "w", stdout);
scanf("%s", buf);
M = strlen(buf);
hsh BlaM = 1;
for (int i = 1; i <= M; ++i)
BlaM *= B;
hsh H = 0;
for (int i = 0; i < M; ++i)
H = H * B + buf[i];
scanf("%s", buf);
N = strlen(buf);
if (N < M) {
puts("0");
return 0;
}
hsh curH = 0;
for (int i = 0; i < M; ++i)
curH = curH * B + buf[i];
for (int i = M;; ++i) {
if (curH == H) {
if (mnr < MAXM)
m[mnr] = i - M;
++mnr;
}
if (i == N)
break;
curH = curH * B + buf[i] - buf[i - M] * BlaM;
}
printf("%d\n", mnr);
for (int i = 0, lim = (mnr < MAXM) ? mnr : MAXM; i < lim; ++i)
printf("%d ", m[i]);
puts("");
return 0;
}