Pagini recente » Cod sursa (job #3136439) | Cod sursa (job #1104578) | Cod sursa (job #769289) | Cod sursa (job #464429) | Cod sursa (job #313985)
Cod sursa(job #313985)
#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)
{
++num;
if(num<=1000)
sol[++l]=i-j;
j=kmpshift[j];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
char c;
long i=0;
scanf("%s",&y);
scanf("%s",&x);
n=strlen(x);
m=strlen(y);
KMP(x,y,n,m);
printf("%ld\n",num);
for(i=1;i<=num;++i)
printf("%ld ",sol[i]);
return 0;
}