Pagini recente » Cod sursa (job #2158171) | Cod sursa (job #819216) | Cod sursa (job #1932749) | Cod sursa (job #1562375) | Cod sursa (job #1482633)
#include<cstdio>
#include<cstring>
using namespace std;
char a[2000010],b[2000010];
int prefix[2000010],sol[2000010],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,j,k;
scanf("%s%s",&a,&b);
m=strlen(a);
n=strlen(b);
for(i=n;i>=1;i--)
a[i]=a[i-1];
a[0]=NULL;
for(i=m;i>=1;i--)
b[i]=b[i-1];
b[0]=NULL;
solve_prefix();
i=j=k=1;
while(n-k>=m){
while(j<=m&&b[i]==a[j]){
i++;
j++;
}
if(j>m){
sol[0]++;
sol[sol[0]]=k;
}
if(prefix[j-1]>0)
k=i-prefix[j-1];
else{
if(i==k)
i++;
k=i;
}
if(j>1)
j=prefix[j-1]+1;
}
printf("%d\n",sol[0]);
for(i=1;i<=sol[0];i++)
printf("%d ",sol[i]);
return 0;
}