Pagini recente » Cod sursa (job #2910163) | Cod sursa (job #1173405) | Cod sursa (job #2830343) | Cod sursa (job #2914213) | Cod sursa (job #1252794)
#include<cstdio>
#include<cstring>
int a[2000005],d[2000005],i,n,m,k,c,nr;
char x[2000005],y[2000005];
using namespace std;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(x+1);
gets(y+1);
// x[0]=' ';
// y[0]=' ';
n=strlen(x+1);
k=0;
a[1]=0;
for(i=2;i<=n;i++)
{
while (k>0&&x[i]!=x[k+1])
{
k=a[k];
}
if (x[i]==x[k+1]) k=k+1;
a[i]=k;
}
m=strlen(y+1);
for(i=1;i<=m;i++)
{
while (k>0&&y[i]!=x[k+1])
{
k=a[k];
}
if (y[i]==x[k+1]) k=k+1;
d[i]=k;
}
for (i=1;i<=m;i++)
{
if (d[i]==n) nr++;
}
printf("%d\n",nr);
nr=0;
for (i=1;i<=m;i++)
{
if (d[i]==n)
{
printf("%d ",i-n);
nr++;
if (nr==1000) break;
}
}
return 0;
}