Pagini recente » Cod sursa (job #2468984) | Cod sursa (job #2907625) | Cod sursa (job #3000461) | Cod sursa (job #1889205) | Cod sursa (job #1518151)
#include<cstdio>
#include<cstring>
#define N1 100007
#define N2 100021
char s[2000001],p[2000001];
int v[1001];
int main(){
int nr1,nr2,nnr1,nnr2, i,k1,k2,x1=1,x2=1,k;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",&p,&s);
nr1=nr2=0;
k1=strlen(p);
k2=strlen(s);
for(i=0;i<k1;i++){
nr1=(nr1*123+p[i])%N1;
nr2=(nr2*123+p[i])%N2;
if(i>=1){
x1=(x1*123)%N1;
x2=(x2*123)%N2;
}
}
if(k1>k2){
printf("0");
return 0;
}
nnr1=nnr2=0;
for(i=0;i<k1;i++){
nnr1=(nnr1*123+s[i])%N1;
nnr2=(nnr2*123+s[i])%N2;
}
k=0;
if(nr1==nnr1&&nr2==nnr2){
k++;
v[k]=0;
}
for(i=k1;i<k2;i++){
nnr1=(((nnr1-(s[i-k1]*x1)%N1+N1)%N1)*123+s[i])%N1;
nnr2=(((nnr2-(s[i-k1]*x2)%N2+N2)%N2)*123+s[i])%N2;
if(nr1==nnr1&&nr2==nnr2){
k++;
if(k<=1000)
v[k]=i-k1+1;
}
}
printf("%d\n",k);
for(i=1;i<=k&&i<=1000;i++)
printf("%d ",v[i]);
return 0;
}