Pagini recente » Cod sursa (job #1979824) | Cod sursa (job #3102) | Cod sursa (job #1373977) | Cod sursa (job #405843) | Cod sursa (job #293071)
Cod sursa(job #293071)
#include<stdio.h>
#include<string.h>
char a[2000004],b[2000004];
int i,km[2000004],nr,bun[1111],n,m;
void prefix()
{ km[1]=0;
int k=0;
for(int y=2;y<=n;y++)
{ while(a[k+1]!=a[y]&&k>0)
k=km[k];
if(a[k+1]==a[y])
k++;
km[y]=k;
}
}
void KMP()
{ prefix();
int q=0;
for(int y=1;y<=m;y++)
{ while(b[y]!=a[q+1]&&q>0)
q=km[q];
if(b[y]==a[q+1])
q++;
if(q==n)
{ if(nr<=1000)
bun[nr]=y-n;
nr++;
}
}
}
int main()
{ freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",a);
scanf("%s",b);
n=strlen(a)-1;
m=strlen(b)-1;
nr=1;
for(i=n;i>=0;i--)
a[i+1]=a[i];
a[0]=' ';
n++;
for(i=m;i>=0;i--)
b[i+1]=b[i];
m++;
b[0]=' ';
KMP();
printf("%d\n",nr-1);
for(i=1;i<=nr-1&&i<=1000;i++)
printf("%d ",bun[i]);
return 0;}