Google Kickstart Round E Problem C Hashing based solution

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int long long
#define pb push_back
#define ff first
#define ss second
const int N=3e5+7;
const long long mod=1e9+7;
const double eps=1e-6;
const double pi=    3.14159265358979323846;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    op_set;

long long binpow(long long base,long long ex)
{
    long long ans=1ll;
    while(ex>0)
    {
        if(ex%2==1)
            ans=(ans*base)%mod;
        base=(base*base)%mod;
        ex=ex/2;
    }
    return ans;
}

int32_t main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   int t;
   cin >> t;

   for(int tc=1;tc<=t;tc++)
   {
        cout << "Case #" << tc << ": ";

        int n;
        string s;
        cin >> n >> s;

        vector<long long> pre(n+2);
        vector<long long> suf(n+2);
        vector<long long> power(n+2);
        power[0]=1;
        for(int i=1;i<=n;i++)
                power[i]=(power[i-1]*31ll)%mod;

        pre[0]=0;
        for(int i=1;i<=n;i++)
        {
            long long rep=s[i-1]-'a'+1;
            pre[i]=(rep*power[i]+pre[i-1])%mod;
        }

        suf[n+1]=0;
        for(int i=n;i>=1;i--)
        {
            long long rep=s[i-1]-'a'+1;
            suf[i]=(rep*power[n+1-i]+suf[i+1])%mod;
        }

        int ans=n;
        for(int len=1;len<=n;len++)
        {
            long long p1=pre[len];
            long long p2=( (suf[1]-suf[len+1]+mod)%mod * binpow(power[n-len],mod-2) )%mod;

            if(p1==p2)
            {
                long long s1=suf[len+1];
                long long s2=( (pre[n]-pre[len]+mod)%mod * binpow(power[len],mod-2) )%mod;

                if(s1==s2)
                {
                    ans=len;
                    break;
                }
            }
        }

        cout << s.substr(0,ans) << "\n";
    }
}


/*
https://www.youtube.com/watch?v=9pV5HjeVrAg
Just Wow.
*/