Pagini recente » Cod sursa (job #681238) | Cod sursa (job #1608343) | Cod sursa (job #331571) | Cod sursa (job #2620220) | Cod sursa (job #704298)
Cod sursa(job #704298)
#include<stdio.h>
#include<string.h>
char a[2000002],c;
int n,b[1002],pi[200002],m,i,q;
void make_prefix();
int main()
{
freopen("kmp.in","r",stdin);
freopen("kmp.out","w",stdout);
scanf("%s\n",&a);
n=strlen(a);
pi[0]=-1;
pi[1]=-1;
q=0;
make_prefix();
for(i=0;!feof(stdin);i++)
{
scanf("%c",&c);
for(;q>=0&&a[q+1]!=c;q=pi[q]);
if(a[q+1]==c)
q++;
if(q==n-1)
{
q=pi[n];
m++;
if(m<=1000)
b[m]=i-n;
else
break;
}
}
printf("%d\n",m);
for(i=1;i<=m;i++)
printf("%d ",b[i]+1);
return 0;
}
void make_prefix()
{
for(i=2;i<n;i++)
{
for(;q>=0&&a[q+1]!=a[i];q=pi[q]);
if(a[q+1]=a[i])
q++;
pi[i]=q;
}
}