#include #include using namespace std; #define mp make_pair #define REP(A,B) for(int (A)=0;(A)<(B);(A)++) #define ll long long #define lld long double typedef pair pli; #define pb push_back typedef vector vi; struct SuffixArray { vi a; string s; SuffixArray(const string& _s) : s(_s + '\0') { int N = s.size(); vector b(N); a.resize(N); REP(i, N) { b[i].first = s[i]; b[i].second = i; } int q = 8; while((1<= N) break; REP(i, N) { b[i].first = (ll)a[i]< arr = SuffixArray(S).a; vector oarr; int poradi = 0; REP(i, 2*n+1) { if(arr[i] < n) { hodn[arr[i]] = poradi++; oarr.pb(arr[i]); } } set< pair > sset; REP(i, k-1) { sset.insert(mp(hodn[(-1-i+n)%n], (-1-i+n)%n)); } int ans = -1; int ansi = -1; REP(i, n) { //printf("ins %d\n", i); sset.insert(mp(hodn[i], i)); auto it = sset.begin(); //printf("i=%d, it->first = %d\n", i, it->first); if(it->first > ans) { ans = max(ans, it->first); ansi = oarr[it->first]; // printf("new maximum at i=%d: (%d, %d)\n", i, it->first, it->second); } sset.erase(sset.find(mp(hodn[(i-k+1+n)%n], (i-k+1+n)%n))); //printf("del %d\n", (i-k+1+n)%n); } REP(i, k) printf("%c", S[(ansi+i)%n]); printf("\n"); return 0; }