Pagini recente » Cod sursa (job #2314399) | Cod sursa (job #1378553) | Cod sursa (job #683911) | Cod sursa (job #333754) | Cod sursa (job #369057)
Cod sursa(job #369057)
#include <stdio.h>
#include <string.h>
long nr=0,sol[1002];
void preKMP (char *x,int m,int KMPshift[])
{ int 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,int n,int m)
{ int i,j;
long KMPshift[2000002];
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)
{nr++;
if (nr<=1000) sol[nr]=i-j;
j=KMPshift[j];
}
}
}
int main ()
{ freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
char x[2000002];
char y[2000002];
long n,m,i;
gets(y);
gets(x);
n=strlen (x);
m=strlen (y);
KMP (x,y,n,m);
printf ("%ld\n",nr);
if (nr<=1000)
for (i=1;i<=nr;i++)
printf ("%ld ",sol[i]);
else
for (i=1;i<=1000;i++)
printf ("%ld ",sol[i]);
return 0;
}