Pagini recente » Cod sursa (job #556117) | Cod sursa (job #1000925) | Cod sursa (job #1560862) | Cod sursa (job #2108118) | Cod sursa (job #1827454)
#include <bits/stdc++.h>
#define maxN 2000002
#define maxA 1001
using namespace std;
FILE *fin = freopen("strmatch.in", "r", stdin);
FILE *fout = freopen("strmatch.out", "w", stdout);
int n, m, v[maxA], z[maxN], ans;
char a[maxN], b[maxN];
void read()
{
gets(a + 1);
gets(b + 1);
}
void zpref()
{
int k, j, L = 0, R = 0;
n = strlen(a + 1);
for (k = 2; k <= n; ++ k)
{
if (k > R)
{
for (j = 1; a[j] == a[k + j - 1]; ++ j)
++ z[k];
L = k;
R = k + z[k] - 1;
}
else
{
int K = k - L + 1;
if (z[K] < R - k + 1)
z[k] = z[K];
else
{
int q = R + 1;
while (a[q] == a[q - k + 1])
++ q;
z[k] = q - k;
R = q - 1;
L = k;
}
}
}
}
void get_ans()
{
int k, j, L = 0, R = 0, Z = 0, r;
m = strlen(b + 1);
for (k = 2; k <= m; ++ k)
{
r = R;
Z = 0;
if (k > R)
{
for (j = 1; a[j] == b[k + j - 1]; ++ j)
++ Z;
L = k;
R = k + Z - 1;
}
else
{
int K = k - L + 1;
if (z[K] < R - k + 1)
Z = z[K];
else
{
int q = R + 1;
while (b[q] == a[q - k + 1])
++ q;
Z = q - k;
R = q - 1;
L = k;
}
}
if (R - L + 1 == n && R != r)
{
++ ans;
if (v[0] < maxN)
v[++ v[0]] = L;
}
}
}
void solve()
{
zpref();
get_ans();
}
void write()
{
printf("%d\n", ans);
for (int i = 1; i <= v[0]; ++ i)
printf("%d ", v[i] - 1);
}
int main()
{
read();
solve();
write();
return 0;
}