Pagini recente » Cod sursa (job #2796027) | Cod sursa (job #2466674) | Cod sursa (job #2796709) | Cod sursa (job #528181) | Cod sursa (job #1076067)
#include<fstream>
#include<cstring>
#define dim 2000003
#define mod1 100007
#define mod2 100021
#define b 83
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char A[dim],B[dim];
int i,j,n,m,sol,cnt,sir[1040];
int ha1,ha2,hb1,hb2,p1,p2;
int main () {
f>>(A);
f>>(B);
n=strlen(A);
m=strlen(B);
if(n>m){
g<<0;
return 0;
}
p1=p2=1;
ha1=ha2=0;
for(i=0;i<n;++i){
ha1=(ha1*b+A[i])%mod1;
ha2=(ha2*b+A[i])%mod2;
if(i!=1){
p1=(p1*b)%mod1;
p2=(p2*b)%mod2;
}
}
hb1=hb2=0;
for(i=0;i<n;++i){
hb1=(hb1*b+B[i])%mod1;
hb2=(hb2*b+B[i])%mod2;
}
if(ha1==hb1 && hb2==ha2){
sir[1]=1;
cnt=1;
}
for(i=n;i<m;++i){
hb1=(((hb1-(B[i-n])*p1)%mod1+mod1)*b+B[i])%mod1;
hb2=(((hb2-(B[i-n])*p2)%mod2+mod2)*b+B[i])%mod2;
if(ha1==hb1 && hb2==ha2){
sir[++cnt]=i-n+1;
}
}
if(cnt>1000)
g<<1000;
else
g<<cnt;
g<<"\n";
for(i=1;i<=cnt ;++i){
g<<sir[i]<<" ";
if(cnt==1000){
break;
}
}
return 0;
}