Pagini recente » Cod sursa (job #1904147) | Cod sursa (job #289220) | Cod sursa (job #1995439) | Cod sursa (job #1956935) | Cod sursa (job #1199858)
#include<cstdio>
using namespace std;
char a[2000001],b[2000001];
int pred[2000001];
int rez[2000001];
int main(){
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
int n,m,i,k,cnt;
scanf ("%s\n",a+1);
scanf ("%s",b+1);
n=0;
while(b[n+1]!='\0') n++;
m=0;
while(a[m+1]!='\0') m++;
pred[1]=0;
k=0;
for(i=2;i<=m;i++){
while(k>0 &&a[k+1]!=a[i]) k=pred[k];
if (a[k+1]==a[i]) k++;
pred[i]=k;
}
k=0;
cnt=0;
for(i=1;i<=n;i++){
while(cnt>0 &&a[cnt+1]!=b[i]) cnt=pred[cnt];
if (a[cnt+1]==b[i]) cnt++;
if (cnt==m){
k++;
rez[k]=i-m;
cnt=pred[cnt];
}
}
printf ("%d\n",k);
if (k>1000) k=1000;
for(i=1;i<=k;i++)
printf ("%d ",rez[i]);
return 0;
}