Minimum Cyclic Shift
(string/min_cyclic_shift.hpp)

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Include: #include "string/min_cyclic_shift.hpp"

Code

#pragma once
#include <string>
#include <vector>

/**
 * @brief Minimum Cyclic Shift
 */

template <typename T>
std::vector<T> min_cyclic_shift(const std::vector<T>& s) {
    const int n = s.size();
    auto ss = s;
    ss.insert(ss.end(), s.begin(), s.end());
    int i = 0, ans = 0;
    while (i < n) {
        ans = i;
        int j = i + 1, k = i;
        while (j < 2 * n && ss[k] <= ss[j]) {
            if (ss[k] < ss[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k) i += j - k;
    }
    return std::vector<T>(ss.begin() + ans, ss.begin() + ans + n);
}

std::string min_cyclic_shift(const std::string& s) {
    auto res = min_cyclic_shift(std::vector<char>(s.begin(), s.end()));
    return std::string(res.begin(), res.end());
}

#line 2 "string/min_cyclic_shift.hpp"
#include <string>
#include <vector>

/**
 * @brief Minimum Cyclic Shift
 */

template <typename T>
std::vector<T> min_cyclic_shift(const std::vector<T>& s) {
    const int n = s.size();
    auto ss = s;
    ss.insert(ss.end(), s.begin(), s.end());
    int i = 0, ans = 0;
    while (i < n) {
        ans = i;
        int j = i + 1, k = i;
        while (j < 2 * n && ss[k] <= ss[j]) {
            if (ss[k] < ss[j])
                k = i;
            else
                k++;
            j++;
        }
        while (i <= k) i += j - k;
    }
    return std::vector<T>(ss.begin() + ans, ss.begin() + ans + n);
}

std::string min_cyclic_shift(const std::string& s) {
    auto res = min_cyclic_shift(std::vector<char>(s.begin(), s.end()));
    return std::string(res.begin(), res.end());
}

Back to top page