Pagini recente » Monitorul de evaluare | Cod sursa (job #2016303) | Cod sursa (job #1666) | Monitorul de evaluare | Cod sursa (job #1776546)
# include <bits/stdc++.h>
using namespace std;
const int Nmax = 2000000 + 5;
int pw[Nmax], i, sol = 0, v[1005], hash_a = 0, hash_b = 0, m, n, N;
char x[Nmax], y[Nmax];
void power()
{
pw[0] = 1;
for (i = 1; i <= n; ++i)
pw[i] = pw[i - 1] * 27;
}
void build()
{
for (i = 1; i <= m; ++i)
hash_a += x[i] * pw[i];
for (i = 1; i <= n; ++i)
{
hash_b += y[i] * pw[i];
if (i < m) continue;
if (hash_a * pw[i - m] == hash_b)
{
++sol;
if (sol <= 1000) v[++N] = i - m;
}
hash_b -= pw[i - m + 1] * y[i - m + 1];
}
}
int main ()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
gets(x + 1), gets(y + 1);
m = strlen(x + 1), n = strlen(y + 1);
if (m > n) {
printf("0\n");
return 0;
}
power();
build();
printf("%d\n", sol);
for (i = 1; i <= N; ++i)
printf("%d ", v[i]);
return 0;
}