Given the problem below: Find the lexicographically minimum cyclic shift of a binary string s of length n ($$$n\leq 3*10^4$$$). A normal brute force solution runs in only 0.05s:
string x = s;
for (int i = 1; i < s.size(); i++)
{
string x2 = string(s.begin() + i, s.end()) + string(s.begin(), s.begin() + i);
if (x2 < x)
x = x2;
}
cout << x << endl;
I only know an $$$O(n^2)$$$ algorithm (the algorithm above) or $$$O(n^2/w)$$$ using bitsets. Is this the intended solution, or is there any better algorithm?
Are you finding: Suffix Array
I have found an $$$O(n)$$$ algorithm after searching for it online: https://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotation.
It's Here
Suffix Automaton also works