Pagini recente » Cod sursa (job #2545508) | Cod sursa (job #643942) | Cod sursa (job #962424) | Cod sursa (job #3359560) | Cod sursa (job #3359557)
#include <bits/stdc++.h>
using namespace std;
const long long base=27;
const long long mod=1e9+7;
const int nmax=2e6+5;
long long coda[nmax],codb[nmax],p[nmax];
int sol[nmax];
void encode(string s,long long cod[]){
int n=s.size();
cod[0]=s[0]-'a';
for(int i=1;i<n;i++){
cod[i]=(base*cod[i-1]%mod+(s[i]-'a'))%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,coda);
encode(b,codb);
p[0]=1;
for(int i=1;i<=m;i++)
p[i]=p[i-1]*base%mod;
long long hasha=coda[n-1];
int cnt=0;
for(int st=0;st+n-1<m;st++){
int dr=st+n-1;
long long hashc;
if(st==0){
hashc=codb[dr];
}
else
hashc=(codb[dr]-codb[st-1]*p[n]%mod+mod)%mod;
if(hashc==hasha){
sol[cnt]=st;
cnt++;
}
}
fout<<cnt<<'\n';
for(int i=0;i<cnt && i<1000;i++){
fout<<sol[i]<<" ";
}
return 0;
}