Pagini recente » Cod sursa (job #2751734) | Cod sursa (job #2542089) | Cod sursa (job #2228694) | Cod sursa (job #1861197) | Cod sursa (job #369043)
Cod sursa(job #369043)
#include<stdio.h>
#include<string.h>
#define LMAX 2000005
long n,m,num,k[LMAX],s[1005];
char x[LMAX],y[LMAX];
void prekmp(long k[])
{
long i,j;
i=0;
j=-1;
k[0]=j;
while(i<m)
{
while(j!=-1 && x[i]!=x[j])
j=k[j];
++i;
++j;
if(x[i]==x[j])
k[i]=k[j];
else
k[i]=j;
}
}
void kmp()
{
long i,j;
prekmp(k);
i=j=0;
while(i<n && num<=1000)
{
while(j!=-1 && x[j]!=y[i])
j=k[j];
++i;
++j;
if(j>=m)
{
if(num<=1000)
{++num;s[num]=i-j;}
j=k[j];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i;
gets(x);
gets(y);
n=strlen(y);
m=strlen(x);
kmp();
printf("%ld\n",num);
for(i=1;i<=num;++i)
printf("%ld ",s[i]);
return 0;
}