Pagini recente » Cod sursa (job #1141183) | Cod sursa (job #108688) | Cod sursa (job #84623) | Cod sursa (job #3287443) | Cod sursa (job #559777)
Cod sursa(job #559777)
#include<cstring>
#include<fstream>
#include<cstdio>
char a[2000000+10],b[2000000+10];
int pi[2000000+10];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(a+1,2000000+5,stdin);
//char tmp=fgetc(stdin);
fgets(b+1,2000000+5,stdin);
int n,m;
n=strlen(a+1);
m=strlen(b+1);
a[n--]='\0';
b[m--]='\0';
pi[1]=0;
int k=0;
for(int i=2;i<=n;++i)
{
while(k>0 && a[i]!=a[k+1])
k=pi[k];
if(a[i]==a[k+1])
++k;
pi[i]=k;
}
k=0;
int nr=0;
int pos[1001]={0};
for(int i=2;i<=m;++i)
{
while(k>0 && a[k+1]!=b[i])
k=pi[k];
if(a[k+1]==b[i])
++k;
if(k==n)
{
++nr;
if(pos[0]<1000)
{
pos[++pos[0]]=i-n;
}
}
}
fprintf(stdout,"%d\n",nr);
for(int i=1;i<=pos[0];++i)
fprintf(stdout,"%d ",pos[i]);
return 0;
}