Pagini recente » Monitorul de evaluare | Cod sursa (job #848020) | Cod sursa (job #1831845) | Cod sursa (job #340241) | Cod sursa (job #1827504)
#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 + 2], z[maxN], ans, Z[maxN];
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 <= n && (k + j - 1) <= n; ++ 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 <= n)
++ q;
z[k] = q - k;
R = q - 1;
L = k;
}
}
}
}
void get_ans()
{
int k, j, L = 0, R = 0, r;
bool ok = 1;
m = strlen(b + 1);
for (k = 1; k <= n; ++ k)
if (a[k] != b[k])
{
ok = 0;
break;
}
if (ok)
{
++ ans;
if (v[0] < maxN)
v[++ v[0]] = 1;
}
for (k = 2; k <= m; ++ k)
{
r = R;
Z[k] = 0;
if (k > R)
{
for (j = 1; a[j] == b[k + j - 1] && j <= n && (k + j - 1) <= m; ++ 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 (b[q] == a[q - k + 1] && q <= m && (q - k + 1) <= n)
++ q;
Z[k] = q - k;
R = q - 1;
L = k;
}
}
if (R - L + 1 == n && R != r)
{
++ ans;
if (v[0] < maxA)
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;
}