Pagini recente » Cod sursa (job #287246) | Cod sursa (job #1895810) | Cod sursa (job #2561310) | Cod sursa (job #376894) | Cod sursa (job #331957)
Cod sursa(job #331957)
#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()
{
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();
printf("%ld\n",num);
for(i=1;i<=num;++i)
printf("%ld ",sol[i]);
return 0;
}