a_gt3_rs's blog

By a_gt3_rs, history, 4 weeks ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Are you finding: Suffix Array

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's Here

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Suffix Automaton also works