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ó

Câu 9: 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.

Trả lờ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;

}