Cod sursa(job #701996)
#include <cstring>
#include <cstdio>
#include <cmath>
const int mx = 2000002;
int n;
int m;
char a[mx];
char b[mx];
int k[mx];
void create() {
for (int i = 1; i < n; ++i) {
int p = k[i - 1];
if (a[i] == a[p]) {
k[i] = p + 1;
} else if (a[i] == a[0]) {
k[i] = 1;
} else {
k[i] = 0;
}
}
}
int num;
int s[1001];
int main() {
FILE * in = fopen("strmatch.in", "rt");
FILE * out = fopen("strmatch.out", "wt");
n = strlen(fgets(a, mx, in)) - 1;
m = strlen(fgets(b, mx, in)) - 1;
create();
int l = 0;
for (int i = 0; i < m; ++i) {
if (b[i] == a[l]) {
if (++l == n) {
if (++num <= 1000) {
s[num] = i - n + 1;
}
l = k[l - 1];
}
} else {
if (l) {
l = k[l - 1];
--i;
}
}
}
fprintf(out, "%d\n", num);
int dist = num < 1000 ? num : 1000;
for (int i = 1; i <= dist; ++i) {
fprintf(out, "%d ", s[i]);
}
fclose(in);
fclose(out);
}