Pagini recente » Cod sursa (job #2082167) | Cod sursa (job #538255) | Cod sursa (job #2243878) | Cod sursa (job #2423077) | Cod sursa (job #369062)
Cod sursa(job #369062)
#include <stdio.h>
#include <string.h>
long nr=0,sol[1002];
char x[2000002];
char y[2000002];
long KMPshift[2000002];
long n,m;
void preKMP ()
{ long i,j;
i=0;
j=KMPshift[0]=-1;
while (i<m)
{ while (j>-1&&y[i]!=y[j])
j=KMPshift[j];
++i;
++j;
if (y[i]==y[j])
KMPshift[i]=KMPshift[j];
else
KMPshift[i]=j;
}
}
void KMP ()
{ long i,j;
//long KMPshift[2000002];
preKMP ();
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 i;
gets(y);
gets(x);
n=strlen (x);
m=strlen (y);
KMP ();
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;
}