Pagini recente » Cod sursa (job #2661416) | Cod sursa (job #1909961) | Cod sursa (job #3240333) | Cod sursa (job #1024771) | Cod sursa (job #505672)
Cod sursa(job #505672)
# include <stdio.h>
# include <string.h>
# define maxl 2001000
char a[2001000],b[2001000];
int pi[2001000],d[2001000],nr,n,m,q,i,k;
inline void creare ()
{
int i;
k=0;
pi[1]=0;
for (i=2; i<=m; i++)
{
while (k>0 && b[k+1]!=b[i])
k=pi[k];
if (b[i]==b[k+1])
k++;
pi[i]=k;
}
}
int main ()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
fgets (b+1,maxl,stdin);
fgets (a+1,maxl,stdin);
n=strlen(a+1)-1;
m=strlen(b+1)-1;
creare();
q=0;
for (i=1; i<=n; i++)
{
while (q>0 && b[q+1]!=a[i])
q=pi[q];
if (b[q+1]==a[i]) q++;
if (q==m){
q = pi[q];
d[++nr]=i-m;
}
if (nr>1010) break;
}
printf ("%d\n",nr);
if (nr>1000)
{
for (i=1; i<=1000; i++)
printf ("%d ",d[i]);
printf ("\n");
}
else
{
for (i=1; i<=nr; i++)
printf ("%d ",d[i]);
printf ("\n");
}
return 0;
}