CSES - Shared codeLink to this code:
https://cses.fi/paste/335daa83c0e2020d12188a/
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define int long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define mii map<int,int>
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zrobits(x) __builtin_ctzll(x)
#define mod 1000000007
#define inf 1e18
#define ps(x,y) cout<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define w(x) int x; cin>>x; while(x--)
#define pw(b,p) pow(b,p) + 0.1
#define endl "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void __print(int32_t x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
char myHeap[200 * 1024 * 1024];
int sz = 0;
void assert_tle(bool q) { while (!q); }
void* operator new ( std::size_t count ) {
sz += count;
assert_tle(sz <= 200 * 1024 * 1024);
return myHeap + sz - count;
}
void operator delete (void *ptr) { }
void fastIO()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
struct stringhash{
int p;
int m1;
int m2;
vector<int> v1,v2;
vector<int> p1;
vector<int> p2;
int sz;
void init(string &str)
{
int p=233;
m1=1e9+7;
m2=998244353;
sz=str.size();
v1.assign(sz+1,0);
v2.assign(sz+1,0);
p1.assign(sz+1,1);
p2.assign(sz+1,1);
for(int i=1;i<=sz;i++)
{
p1[i]=p*p1[i-1];
p1[i]%=m1;
p2[i]=p*p2[i-1];
p2[i]%=m2;
v1[i]=str[i-1]+v1[i-1]*p;
v1[i]%=m1;
v2[i]=str[i-1]+v2[i-1]*p;
v2[i]%=m2;
}
}
pii retval(int i,int r)
{
return{(v1[r+1]-((v1[i]*p1[r-i+1])%m1)+m1)%m1,(v2[r+1]-(v2[i]*(p2[r-i+1])%m2)+m2)%m2};
}
};
void solve()
{
string str;
cin>>str;
int n=str.size();
str+=str;
stringhash h;
h.init(str);
int ans=0;
int ct=0;
for(int i=1;i<n;i++)
{
int low=1;
int high=n-1;
int c=0;
while(high>=low)
{
int len=(high+low)/2;
// debug(i,len,ct++);
ct++;
if(h.retval(ans,ans+len-1)==h.retval(i,i+len-1))
{
low=len+1;
c=len;
}
else
{
high=len-1;
}
}
if(str[i+c]<str[ans+c])
ans=i;
}
debug(ct);
cout<<str.substr(ans,n);
}
int32_t main()
{
fastIO();
//w(t)
{
solve();
cout<<endl;
}
return 0;
}