Ukkonen's algorithm. Linearization of a cyclic string

If you list all the cyclic shifts of a string, then is lexicographically minimal and will be what

 abbab
 bbaba
 babab
 ababb //  вот оно
 babba

If you need to use a suffix tree (or array), you can list it in lex. order suffixes for a doubled string (tree traversal or suffix traversal).array), and choose the smallest one whose length is not less than the length of the original string, and take from it a piece with the length of the string

abba+abba = abbaabba

Suffixes

a
aabba   //вот оно, берём aabb
abba
abbaabba
ba
baabba
bba
bbaabba

In addition, for finding the minimum cyclic cut is a simple linear Duval algorithm, which builds the Lindon decomposition for a doubled string (abbababbab), this is easier than building a suffix tree.

string min_cyclic_shift (string s) {
    s += s;
    int n = (int) s.length();
    int i=0, ans=0;
    while (i < n/2) {
        ans = i;
        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)  i += j - k;
    }
    return s.substr (ans, n/2);