Pagini recente » Cod sursa (job #2531388) | Cod sursa (job #1402214) | Cod sursa (job #386776) | Cod sursa (job #1101424) | Cod sursa (job #1299964)
#include <cstdio>
#include <cstring>
#define Nmax 4000005
using namespace std;
char a[Nmax],b[Nmax];
int Z[Nmax],N,M,sol[Nmax];
inline void ZAlgorithm()
{
int L=0,R=0,i,k;
for(i=2;i<=N;++i)
if(i>R)
{
L=i;
for(R=i;R<=N && R-L+1<=M && a[R]==a[R-L+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; ++R;
for(;R<=N && R-L+1<=M && a[R]==a[R-L+1];++R);
--R;
Z[i]=R-L+1;
}
}
}
inline void ConCat()
{
for(int i=1;i<=M;++i)
a[N+i]=b[i];
N+=M;
}
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-M+1;i<=N;++i)
if(Z[i]>=N-M)
sol[++sol[0]]=i-(N-M)-1;
printf("%d\n", sol[0]);
for(i=1;i<=sol[0] && i<=1000;++i)
printf("%d ", sol[i]);
printf("\n");
return 0;
}