Pagini recente » Cod sursa (job #1177430) | Cod sursa (job #1165757) | Cod sursa (job #1662780) | Cod sursa (job #1144638) | Cod sursa (job #342307)
Cod sursa(job #342307)
#include<stdio.h>
#include<string.h>
int n,m,nr;
int sol[1<<10],p[1<<21];
char v[1<<21],s[1<<21];
void prefix()
{
int i,q=0;
p[1]=0;
for(i=2;i<=n;i++)
{
while(q && v[q+1]!=v[i])
q=p[q];
if(v[q+1]==v[i])
q++;
p[i]=q;
}
}
void kmp()
{
int i,q=0;
for(i=1;i<=m;i++)
{
while(q && v[q+1]!=s[i])
q=p[q];
if(v[q+1]==s[i])
q++;
if(q==n)
{
q=p[q];
nr++;
if(nr<=1000)
sol[nr]=i-n;
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(v+1);n=strlen(v+1);
gets(s+1);m=strlen(s+1);
prefix();
kmp();
printf("%d\n",nr);
int i;
if(nr>1000)
nr=1000;
for(i=1;i<=nr;i++)
printf("%d ",sol[i]);
return 0;
}