Pagini recente » Cod sursa (job #2616145) | Cod sursa (job #2990874) | Cod sursa (job #2717718) | Cod sursa (job #2754913) | Cod sursa (job #169927)
Cod sursa(job #169927)
#include<stdio.h>
#include<string.h>
#define N 2000001
char a[N],b[N];
int pi[N],v[1001];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int la,lb,k=0,n=0,i;
scanf("%s",a+1);
scanf("%s",b+1);
la=strlen(a+1);
lb=strlen(b+1);
pi[1]=0;
for(i=2; i<=la; i++)
{
while((k>0)&&(a[k+1]!=a[i]))
k=pi[k];
if(a[k+1]==a[i])
k++;
pi[i]=k;
}
int q=0;
for(i=1; i<=lb; i++)
{
while((q>0)&&(a[q+1]!=b[i]))
q=pi[q];
if(a[q+1]==b[i])
q++;
if(q==la)
{
n++;
v[n]=i-la;
}
}
printf("%d\n",n);
for(i=1; (i<n)&&(i<1000); i++)
printf("%d ",v[i]);
if(n>1000)
n=1000;
printf("%d\n",v[n]);
return 0;
}