#include
#define int long long int
using namespace std;
const int mod=1e9+7;
const int p=31;
int power(int a,int b){
int res=1;
while(b){
if(b & 111){
res*=a;
res%=mod;
}
b/=2;
a*=a;
a%=mod;
}
return res;
}
int stringhash(string s){
int p_power=1;
int newhash=0;
for(int i=0;i<s.size();i++){
newhash+=(p_power*(s[i]-'a'+1));
p_power*=p;
p_power%= mod;
newhash%= mod;
}
return newhash;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
string text=“ababababba”;
string patt=“aba”;
int pat_hash=stringhash(patt);
int n=text.size();
int m=patt.size();
int pref[n];
for(int i=0;i<n;i++){
pref[i]=(text[i]-‘a’+1)*power(p,i);
}
for(int i=1;i<n;i++){
pref[i]+=pref[i=1];
pref[i]%=mod;
}
for(int i=0;i+m<=n;i++){
// substring from s[l…r]
// r=i+m-1;
// l=i
int new_hash=pref[i-m+1];
if(i-1>0){
new_hash-=pref[i-1];
}
new_hash+= mod;
new_hash%= mod;
if(new_hash==(pat_hash*power(p,i))%mod){
cout<<i<<endl;
}
}
return 0;
}