Блог пользователя a_gt3_rs

Автор a_gt3_rs, история, 2 месяца назад, По-английски

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?

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
2 месяца назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Are you finding: Suffix Array

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's Here

»
2 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Suffix Automaton also works