Pagini recente » Cod sursa (job #3151228) | Cod sursa (job #3260815) | Cod sursa (job #2728862) | Cod sursa (job #3233804) | Cod sursa (job #1075807)
#include<fstream>
#include<cstring>
#define dim 2000003
#define mod1 2007
#define mod2 2021
#define b 103
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];
long long ha1,ha2,hb1,hb2,p1,p2;
int main () {
f>>(A+1);
f>>(B+1);
n=strlen(A+1);
m=strlen(B+1);
if(n>m){
g<<0;
return 0;
}
p1=p2=1;
ha1=ha2=0;
for(i=1;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=1;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+1;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;
}
}
if(cnt>1000)
g<<1000;
else
g<<cnt;
g<<"\n";
for(i=1;i<=cnt && cnt<=1000;++i)
g<<sir[i]<<" ";
return 0;
}