Pagini recente » Cod sursa (job #1731342) | Cod sursa (job #3184196) | Cod sursa (job #2511673) | Cod sursa (job #954030) | Cod sursa (job #1409654)
///Z ALGORITHM
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int NMAX = 2000004;
char a[NMAX], b[NMAX];
int sol[1004], lg, n, m, Z[NMAX], dp[NMAX];
inline void Z_Algorithm()
{
int imax = 0, j,i, ii;
Z[1] = 0;
for(i = 2;i<=n;++i)
{
if(i <= imax+Z[imax]-1)
Z[i] = min((imax+Z[imax]-1)-i,Z[i-imax+1]);
for(j = Z[i],ii = i+Z[i];ii <= n && a[j+1] == a[ii];++ii,++j);
Z[i] = j;
if(i+Z[i] > imax+Z[imax])
imax = i;
}
}
inline void Solve()
{
int imax = 0, j,i, ii;
for(i = 1;i+n-1 <= m;++i)
{
if(i <= imax+dp[imax]-1)
dp[i] = Z[i-imax+1];
for(j = dp[i],ii = i+dp[i];ii <= m && j < n && a[j+1] == b[ii];++ii,++j);
dp[i] = j;
if(j == n)
{
++lg;
if(lg <= 1000)
sol[lg] = i-1;
}
if(i+dp[i] > imax+dp[imax])
imax = i;
}
}
inline void Write()
{
printf("%d\n",lg);
lg = min(lg,1000);
for(int i=1;i<=lg;++i)
printf("%d ",sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",(a+1),(b+1));
n = strlen(a+1), m = strlen(b+1);
Z_Algorithm();
Solve();
Write();
return 0;
}