Pagini recente » Cod sursa (job #382403) | Cod sursa (job #81405) | Cod sursa (job #3173426) | Cod sursa (job #300991) | Cod sursa (job #309507)
Cod sursa(job #309507)
#include<stdio.h>
#include<string.h>
long num,n,m,sol[1005];
char x[2000001],y[2000001];
long kmpshift[2000001];;
void preKMP(char x[],long n,long kmpshift[])
{
long i,j;
i=0;
j=kmpshift[0]=-1;
while(i<m)
{
while(j>-1 && x[i]!=x[j])
j=kmpshift[j];
++i;++j;
if(x[i]==x[j])
kmpshift[i]=kmpshift[j];
else
kmpshift[i]=j;
}
}
void KMP(char x[],char y[],long n,long m)
{
long i,j,l=0;
preKMP(y,m,kmpshift);
i=j=0;
while(i<n)
{
while(j>-1 && x[i]!=y[j])
j=kmpshift[j];
++i;++j;
if(j>=m)
{
sol[++l]=i-j;
j=kmpshift[j];
++num;
}
if(num>1000)
return;
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(y);
gets(x);
n=strlen(x);
m=strlen(y);
KMP(x,y,n,m);
printf("%ld\n",num);
long i;
for(i=1;i<=num;++i)
printf("%ld ",sol[i]);
return 0;
}