Pagini recente » Cod sursa (job #1805671) | Cod sursa (job #1595445) | Cod sursa (job #175313) | Cod sursa (job #1011487) | Cod sursa (job #1517599)
#include<stdio.h>
#include<cstring>
#define n1 100007
#define n2 100021
#define b 123
char p[2000001],s[2000001];
int v[2000001];
int main(){
int i,n,k,x,nr,B,nr1,nr2,p1,p2,k1,k2,nnr1,nnr2,j;
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s%s",&p,&s);
k1=strlen(p);
k2=strlen(s);
nr1=nr2=0;
p1=1;
p2=1;
for(i=0;i<k1;i++){
nr1=((nr1*b)%n1+p[i])%n1;
nr2=((nr2*b)%n2+p[i])%n2;
if(i!=0){
p1=(p1*b)%n1;
p2=(p2*b)%n2;
}
}
nnr1=nnr2=0;
for(i=0;i<k1;i++){
nnr1=((nnr1*b)%n1+s[i])%n1;
nnr2=((nnr2*b)%n2+s[i])%n2;
}
k=0;
if(nr1==nnr1&&nr2==nnr2){
k++;
v[k]=0;
}
for(i=0,j=k1;j<k2;i++,j++){
nnr1=((((nnr1-(s[i]*p1))*b)%n1+n1)%n1+s[j])%n1;
nnr2=((((nnr2-(s[i]*p2))*b)%n2+n2)%n2+s[j])%n2;
if(nr1==nnr1&&nr2==nnr2){
k++;
v[k]=i+1;
if(k>=1001)
j=k2;
}
}
printf("%d\n",k);
for(i=1;i<=k&&i<=1000;i++)
printf("%d ",v[i]);
return 0;
}