Tìm cách tách S thành ít nhất các xâu, sao cho mỗi xâu đều là Lyndon word

Tìm cách tách S thành ít nhất các xâu, sao cho mỗi xâu đều là Lyndon word.

Đề bài: Lyndon word là các xâu khác rỗng, mà có thứ tự từ điển nhỏ hơn tất cả các xâu thu được bằng phép xoay của nó.

Cho một xâu S. Tìm cách tách S thành ít nhất các xâu, sao cho mỗi xâu đều là Lyndon word.

Lời giải:

void lyndon(string s) {

          int n = (int) s.length();

          int i = 0;

          while (i < n) {

                   int j = i + 1, k = i;

                   while (j < n && s[k] <= s[j]) {

                             if (s[k] < s[j]) k = i;

                             else ++k;

                             ++j;

                   }

                   while (i <= k) {

                             cout << s.substr(i, j - k) << ' ';

                             i += j - k;

                   }

          }

          cout << endl;

}