Explanation

We'll maintain the smallest lexicographically rotation after it's starting index, let it be $i$. Then, the comparison between this one and another rotation, starting at index $j$, is done by finding the first different character. This can be quickly done by binary searching the value $d$ such that $S_{i+d} \neq S_{j+d}$. Furthermore, hashing can be used to compare the prefixes of the rotations.

The algorithm is also known as Booth's Algorithm.

Implementation

Time Complexity: $\mathcal{O}(N \cdot \log{N})$

Copy
#include <bits/stdc++.h>

using namespace std;

 Code Snippet: Hashing Template (from the module) (Click to expand)

int main() {
	string s;
	cin >> s;