Double Hash (KMP problem)

// NgJaBach: Forever Meadow <3

#include<bits/stdc++.h>

using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long int ll;
typedef unsigned long long ull;
#define pb push_back
#define pob pop_back
#define mp make_pair
#define upb upper_bound
#define lwb lower_bound
#define bend(a) a.begin(),a.end()
#define rev(x) reverse(bend(x))
#define mset(a) memset(a, 0, sizeof(a))
#define fi first
#define se second
#define gcd __gcd
#define getl(s) getline(cin, s);
#define setpre(x) fixed << setprecision(x)
#define endl '\n'
const int N=10000050;
const ll INF=1e18+7,base=311,M=1000000007,M2=1000000009;
pair<ll,ll>operator-(pair<ll,ll>A,pair<ll,ll>B){
    pair<ll,ll>C;
    C.fi=A.fi-B.fi;
    C.se=A.se-B.se;
    return C;
}
pair<ll,ll>operator*(pair<ll,ll>A,pair<ll,ll> B){
    pair<ll,ll>C;
    C.fi=A.fi*B.fi;
    C.se=A.se*B.se;
    return C;
}
int n,m,ans,L,R,mid,pos;
pair<ll,ll>double_bazooka[N],A,B,power[N];
string s;
int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(nullptr); cout.tie(nullptr);
//    freopen("MR.inp","r",stdin);
//    freopen("MR.out","w",stdout);
    cin>>s;
    m=s.size();
    s+=s;
    n=s.size();
    power[0]={1,1};
    for(int i=1;i<=n;++i) power[i]={(power[i-1].fi*base)%M,(power[i-1].se*base)%M2};
    double_bazooka[0]={(s[0]-'a'+1)%M,(s[0]-'a'+1)%M2};
    for(int i=1;i<n;++i) double_bazooka[i]={(double_bazooka[i-1].fi*base+s[i]-'a'+1)%M,(double_bazooka[i-1].se*base+s[i]-'a'+1)%M2};
    ans=0;
    for(int i=m;i<n;++i){
        L=0; R=m-1;
        pos=-1;
        while(L<=R){
            mid=(L+R)/2;
            if(ans==0) A=double_bazooka[ans+mid];
            else A=(double_bazooka[ans+mid]-double_bazooka[ans-1]*power[mid+1]);
            A.fi=(A.fi+M*M)%M; A.se=(A.se+M2*M2)%M2;
            B=(double_bazooka[i-m+1+mid]-double_bazooka[i-m]*power[mid+1]);
            B.fi=(B.fi+M*M)%M; B.se=(B.se+M2*M2)%M2;
            if(A!=B) R=mid-1;
            else{
                L=mid+1;
                pos=max(pos,mid);
            }
        }
        if((pos+1)==m) continue;
        ++pos;
        if(s[ans+pos]>s[i-m+1+pos]) ans=i-m+1;
    }
    for(int i=0;i<m;++i) cout<<s[ans+i];
    return 0;
}
/*
==================================+
INPUT:                            |
------------------------------    |

------------------------------    |
==================================+
OUTPUT:                           |
------------------------------    |

------------------------------    |
==================================+
*/