Pagini recente » Cod sursa (job #1015049) | Cod sursa (job #508880) | Cod sursa (job #153102) | Cod sursa (job #2480895) | Cod sursa (job #1552498)
#include <cstdio>
#include <cstring>
using namespace std;
int nr,n,m,i,k,x[2000004],y[2000004];
char a[2000004],b[2000004];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(a+1);gets(b+1);
n=strlen(a+1);m=strlen(b+1);
x[1]=0;
for(i=2;i<=n;++i)
{
k=x[i-1];
while(k && a[i]!=a[k+1]) k=x[k];
if(a[i]==a[k+1]) x[i]=k+1;
else x[i]=0;
}
for(i=1;i<=m;++i)
{
k=y[i-1];
while(k && b[i]!=a[k+1]) k=x[k];
if(b[i]==a[k+1]) y[i]=k+1;
else y[i]=0;
if(y[i]==n) ++nr;
}
int afs=0;
printf("%d\n",nr);
for(i=n;i<=m && afs<1000;++i) if(y[i]==n) {printf("%d ",i-n);afs++;}
printf("\n");
return 0;
}