Pagini recente » Cod sursa (job #1643975) | Cod sursa (job #1620019) | Cod sursa (job #2326612) | Cod sursa (job #2737922) | Cod sursa (job #3359594)
#include <bits/stdc++.h>
using namespace std;
const int nmax=2000005;
const int base=73;
const int mod1=1000000007;
const int mod2=1000000009;
int coda1[nmax],codb1[nmax],p1[nmax];
int coda2[nmax],codb2[nmax],p2[nmax];
int sol[nmax];
void encode(string s,int cod[],int mod){
int n=s.size();
cod[0]=(int)s[0];
for(int i=1;i<n;i++)
cod[i]=(1LL*base*cod[i-1]+(int)s[i])%mod;
}
int main(){
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a,b;
fin>>a>>b;
int n=a.size(),m=b.size();
encode(a, coda1, mod1);
encode(b, codb1, mod1);
encode(a, coda2, mod2);
encode(b, codb2, mod2);
p1[0]=p2[0]=1;
for(int i=1;i<=m;i++){
p1[i]=1LL*p1[i-1]*base%mod1;
p2[i]=1LL*p2[i-1]*base%mod2;
}
int hasha1=coda1[n-1],hasha2=coda2[n-1],cnt=0;
for(int st=0;st+n-1<m;st++){
int dr=st+n-1;
int hash1,hash2;
if(st==0){
hash1=codb1[dr];
hash2=codb2[dr];
}
else{
hash1=(codb1[dr]-1LL*codb1[st-1]*p1[n]%mod1+mod1)%mod1;
hash2=(codb2[dr]-1LL*codb2[st-1]*p2[n]%mod2+mod2)%mod2;
}
if(hash1==hasha1 && hash2==hasha2){
sol[cnt]=st;
cnt++;
}
}
fout<<cnt<<'\n';
for(int i=0;i<cnt && i<1000;i++)
fout<<sol[i]<<' ';
return 0;
}