Pagini recente » Cod sursa (job #3155646) | Cod sursa (job #628385) | Cod sursa (job #3147875) | Cod sursa (job #2914320) | Cod sursa (job #1552535)
# include <bits/stdc++.h>
using namespace std;
const int Nmax = 2000000 + 5;
int N, i, sol = 0, M, nr = 0;
int phi[Nmax], v[Nmax];
char a[Nmax], b[Nmax];
void PHI()
{
int k;
N = strlen(a+1);
phi[1] = 0;
for (i = 2; i <= N; i++)
{
k = phi[i - 1];
while (k && a[i] != a[k+1])
k = phi[k];
if (a[i] == a[k + 1]) phi[i] = k + 1;
else phi[i] = 0;
}
}
void check()
{
int k;
M = strlen(b + 1);
for (i = 1; i <= M; ++i)
{
k = v[i-1];
while (k && b[i] != a[k+1])
k = phi[k];
if (b[i] == a[k+1]) v[i] = k + 1;
else v[i] = 0;
if (v[i] == N - 1) sol++;
}
}
int main ()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);
gets(b+1);
a[strlen(a+1) + 1] = ' ';
PHI();
check();
printf("%d\n", sol);
for (i = 1; i <= M && nr < 1000; ++i)
if (v[i] == N-1) printf("%d ", i - (N - 1)), ++nr;
printf("\n");
return 0;
}