Is there any better algorithm?

Правка en3, от a_gt3_rs, 2024-10-16 14:51:20

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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский a_gt3_rs 2024-10-16 14:51:37 0 (published)
en3 Английский a_gt3_rs 2024-10-16 14:51:20 0 (saved to drafts)
en2 Английский a_gt3_rs 2024-10-16 14:44:59 1 Tiny change: ' cout << x2 << endl;\' -> ' cout << x << endl;\'
en1 Английский a_gt3_rs 2024-10-16 14:44:09 598 Initial revision (published)