Youthful-Passion-Fruit-teambook

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub AlexanderNekrasov/Youthful-Passion-Fruit-teambook

:warning: strings/MinShift.cpp

Code

/**
 * Author: Iurii Pustovalov
 * Date: 2022-11-08
 * Description: Calculates min-cyclic-shift of s, Duval decomposition
 * Time: O(n)
 */
string minshift(string s) {
    int i = 0, ans = 0;
    s += s;
    int n = s.size();
    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);
}
#line 1 "strings/MinShift.cpp"
/**
 * Author: Iurii Pustovalov
 * Date: 2022-11-08
 * Description: Calculates min-cyclic-shift of s, Duval decomposition
 * Time: O(n)
 */
string minshift(string s) {
    int i = 0, ans = 0;
    s += s;
    int n = s.size();
    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);
}
Back to top page