Pagini recente » Cod sursa (job #3240248) | Cod sursa (job #2086000) | Cod sursa (job #1162886) | Cod sursa (job #2358525) | Cod sursa (job #1482678)
#include<cstdio>
#include<cstring>
char a[2000010],b[2000010];
int prefix[2000010],sol[1010],n,m;
void solve_prefix(){
int i=0,j;
prefix[1]=0;
for(j=2;j<=m;j++){
while(i>0&&a[i+1]!=a[j])
i=prefix[i];
if(a[i+1]==a[j])
i++;
prefix[j]=i;
}
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int i=0,j;
scanf("%s%s",&a,&b);
m=strlen(a);
n=strlen(b);
for(i=m;i>=1;i--)
a[i]=a[i-1];
for(i=n;i>=1;i--)
b[i]=b[i-1];
a[i]=b[i]=NULL;
solve_prefix();
for(j=1;j<=n;j++){
while(i>0&&a[i+1]!=b[j])
i=prefix[i];
if(a[i+1]==b[j])
i++;
if(i==m){
i=prefix[m];
sol[0]++;
if(sol[0]<=1000)
sol[sol[0]]=j-m;
}
}
printf("%d\n",sol[0]);
if(sol[0]>1000)
sol[0]=1000;
for(i=1;i<=sol[0];i++)
printf("%d ",sol[i]);
return 0;
}