Pagini recente » Cod sursa (job #1540173) | Cod sursa (job #2819291) | Cod sursa (job #2666826) | Cod sursa (job #2123815) | Cod sursa (job #313978)
Cod sursa(job #313978)
#include<stdio.h>
#include<string.h>
#define NMAX 10000
#define MMAX 1000
long num,n,m,sol[1005];
char x[NMAX],y[MMAX];
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;
long kmpshift[NMAX];
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;
}
}
}
int main()
{
freopen("f.in","r",stdin);
freopen("f.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;
}