Cod sursa(job #808636)
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int p, t;
int size;
int ans[2000002];
char P[2000002], T[2000002];
vector<int> pre_kmp(char P[], int p) {
vector<int> b(p + 1, 1 << 30);
int i = 0, j = -1;
b[i] = j;
while (i < p) {
while (!(j == -1 || P[i] == P[j])) {
j = b[j];
}
i++;
j++;
b[i] = j;
}
return b;
}
void kmp(char P[], int p, char T[], int t) {
vector<int> b = pre_kmp(P, p);
int i = 0, j = 0;
while (i < t) {
while (!(j == -1 || T[i] == P[j])) {
j = b[j];
}
i++;
j++;
if (j == p) {
ans[size++] = i - j;
j = b[j];
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", P, T);
p = strlen(P);
t = strlen(T);
kmp(P, p, T, t);
printf("%d\n", size);
for (int i = 0; i < min(size, 1000); i++) {
printf("%d ", ans[i]);
}
return 0;
}