Pagini recente » Cod sursa (job #1097000) | Cod sursa (job #41501) | Cod sursa (job #1002468) | Cod sursa (job #81015) | Cod sursa (job #1252792)
#include<cstdio>
#include<string.h>
int nr,i,n,m,k,h,p[2000009],d[2000009];
char x[2000009],y[2000009];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(x+1);
n=strlen(x+1);
gets(y+1);
m=strlen(y+1);
k=0;
p[1]=0;
for(i=2;i<=n;i++)
{
while(k>0&&x[i]!=x[k+1])
k=p[k];
if(x[i]==x[k+1]) k++;
p[i]=k;
}
k=0;
for(i=1;i<=m;i++)
{
while(k>0&&y[i]!=x[k+1])
k=p[k];
if(y[i]==x[k+1]) k++;
d[i]=k;
}
for(i=1;i<=m;i++)
{
if(d[i]==n) nr++;
}
printf("%d\n",nr);
for(i=1;i<=m;i++)
{
if(d[i]==n)
{
h++;
printf("%d ",i-n);
if(h==1000) break;
}
}
return 0;
}