UVA 11512 / Hashing

/***
 created: 2022-01-04-14.17.10
***/

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll mod[2]= {1000007707,1000007909};
ll base[2]= {26,307};
ll hash1[2][1000007];
ll hash2[2][1000007];
ll p1[1000007];
ll p2[1000007];

void pwr()
{
    p1[0]=p2[0]=1;

    for(ll i=1; i<=1000005; i++)
    {
        p1[i]=(p1[i-1]*base[0])%mod[0];
        p2[i]=(p2[i-1]*base[1])%mod[1];
    }
}

void hashing(string a)
{
    ///for string a

    hash1[0][0]=hash1[1][0]=0;

    for(ll i=1; i<=a.size(); i++)
    {
        hash1[0][i]=(hash1[0][i-1]*base[0] + a[i-1])%mod[0];
        hash1[1][i]=(hash1[1][i-1]*base[1] + a[i-1])%mod[1];
    }
}

ll forwardhash(ll l,ll r)
{
    ll x=(hash1[0][r] - hash1[0][l-1]*p1[r-l+1])%mod[0];

    if(x<0) x+=mod[0];

    return x;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    pwr();


    test
    {
        ll n,m=0,i,j,k,l,h,yy=0;

        string a,b="";

        cin>>a;

        hashing(a);

        k=1;

        n=a.size();

        map<ll,ll>x;

        l=1,h=n;

        while(l<=h)
        {
            ll mid=(l+h)/2;


            yy=0;

            for(i=1;i<=n-mid+1;i++)
            {
                 k=forwardhash(i,i+mid-1);

                 x[k]++;

                 if(x[k]>=2)
                 {

                      yy=1;

                      string d=a.substr(i-1,mid);

                      if(mid==b.size())
                      {
                           if(min(b,d)==d)
                           {
                                m=x[k];
                                b=d;
                           }
                      }
                      else if(mid>b.size())
                      {
                           m=x[k];
                           b=d;
                      }
                 }
            }

            if(yy) l=mid+1;
            else h=mid-1;

        }

        if(m==0) cout<<"No repetitions found!"<<nl;
        else cout<<b<<" "<<m<<nl;

    }

    get_lost_idiot;
}