Pagini recente » Cod sursa (job #1737051) | Cod sursa (job #2625624) | Cod sursa (job #2496280) | Cod sursa (job #2287669) | Cod sursa (job #338680)
Cod sursa(job #338680)
#include<stdio.h>
#include<string.h>
#define NMAX 2000005
long n,m,pos[1002],k;
long kmpshift[NMAX];
char x[NMAX],y[NMAX];
void prekmp()
{
int i,j;
j=kmpshift[1]=0;
for(i=2;i<=n;++i)
{
while(j && x[j+1]!=x[i])
j=kmpshift[j];
if(x[i]==x[j+1])
++j;
kmpshift[i]=j;
}
}
void kmp()
{
long i,j=0;
for(i=1;i<=m;++i)
{
while(j && y[i]!=x[j+1])
j=kmpshift[j];
if(x[j+1]==y[i])
++j;
if(j==n-1)
{
++k;
if(k<=1000)
pos[k]=i-n+1;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
long i;
gets(x+1);
gets(y+1);
for(n=1;x[n];++n);
for(m=1;y[m];++m);
prekmp();
kmp();
printf("%ld\n",k);
if(k>1000) k=1000;
for(i=1;i<=k;++i)
printf("%ld ",pos[i]);
printf("\n");
return 0;
}