Pagini recente » Statistici Anton Ionut (aquariusSs) | Cod sursa (job #1556690) | Cod sursa (job #2321598) | Cod sursa (job #2830218) | Cod sursa (job #2095152)
#include <cstdio>
#include <cstring>
using namespace std;
const int MAX_L = 2000000;
char a[MAX_L + 5], b[MAX_L + 5];
char s[2 * MAX_L + 5];
int v[2 * MAX_L + 5];
void Z(int lg) {
int l = 0, r = 0;
for (int i = 1; i <= lg; ++i) {
if (i == 1403)
int ok = 1;
if (i >= r) {
int j = i;
while (j <= lg && s[j - i] == s[j])
j++;
v[i] = j - i;
l = i;
r = j - 1;
} else {
int aux = v[i - l];
int r1 = i + aux - 1;
if (r1 >= r) {
l = r - i;
while (r <= lg && s[l] == s[r])
l++, r++;
v[i] = r - i;
l = i;
r--;
}
}
}
}
int main() {
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
scanf("%s %s", a, b);
int n = strlen(a), m = strlen(b);
for (int i = 0; i < n; ++i)
s[i] = a[i];
s[n] = '*';
for (int i = n + 1; i <= n + m; ++i)
s[i] = b[i - n - 1];
Z(n + m);
int ans = 0;
for (int i = n + 1; i <= n + m; ++i)
if (v[i] == n)
ans++;
printf("%d\n", ans);
int af = 0;
for (int i = n + 1; i <= n + m && af < 1000; ++i)
if (v[i] == n)
printf("%d ", i - n - 1), af++;
return 0;
}