Pagini recente » Cod sursa (job #328012) | Cod sursa (job #884221) | Cod sursa (job #167752) | Cod sursa (job #1342981) | Cod sursa (job #1212711)
#include <cstdio>
#include <cstring>
#define Nmax 4000005
using namespace std;
int N,M,len,Z[Nmax],sol[Nmax];
char a[Nmax],b[Nmax];
inline void Concat()
{
len=N+M;
for(int i=1;i<=M;++i)
a[N+i]=b[i];
}
inline void ZAlgorithm()
{
int L,R,i,k;
Z[1]=len; L=R=0;
for(i=2;i<=len;++i)
if(i>R)
{
L=i;
for(R=i;R<=len && a[R]==a[R-i+1];++R);
--R;
Z[i]=R-L+1;
}
else
{
k=i-L+1;
if(Z[k]<R-i+1)
Z[i]=Z[k];
else
{
L=i;
for(++R;R<=len && a[R]==a[R-i+1];++R);
--R;
Z[i]=R-L+1;
}
}
}
int main()
{
int i;
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
scanf("%s%s", (a+1),(b+1));
N=strlen(a+1); M=strlen(b+1);
Concat();
ZAlgorithm();
for(i=N+1;i<=len;++i)
if(Z[i]>=N)
sol[++sol[0]]=i-N-1;
printf("%d\n", sol[0]);
for(i=1;i<=sol[0] && i<=1000;++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}