Minimum Rotation
(string/minimum_rotation.hpp)

• View this file on GitHub
• Last update: 2026-07-13 05:39:37+09:00
• Include: #include "string/minimum_rotation.hpp"

Overview

minimum_cyclic_shift finds where the lexicographically smallest rotation of a sequence begins. If several starting positions produce the same minimum rotation, it returns the smallest index.

#include "string/minimum_rotation.hpp"

The function is in m1une::string and uses the same Duval-style linear scan as the previous implementation in lyndon_factorization.hpp.

Interface

template <class Sequence>
int minimum_cyclic_shift(const Sequence& sequence);

Function	Description	Complexity
minimum_cyclic_shift(sequence)	Returns the earliest starting index of a lexicographically minimum cyclic shift.	$O(N)$ time and $O(1)$ additional memory

Sequence must provide size() and random access through operator[]. Its elements are compared using operator<. Strings, vectors, and arrays are supported.

The empty sequence returns 0. The function does not construct or modify a rotation; it only returns its starting index.

lyndon_factorization.hpp includes this header, preserving the old include behavior. New code that only needs minimum rotation can include this smaller header directly.

Example

#include "string/minimum_rotation.hpp"

#include <iostream>
#include <string>

int main() {
    std::string text = "banana";
    int start = m1une::string::minimum_cyclic_shift(text);
    std::string rotation = text.substr(start) + text.substr(0, start);

    std::cout << start << '\n';     // 5
    std::cout << rotation << '\n';  // abanan
}

Required by

• String Algorithms Bundle (string/all.hpp)
• Lyndon Factorization (string/lyndon_factorization.hpp)

Verified with

• verify/string/lyndon_factorization.test.cpp
• verify/string/minimum_rotation.test.cpp
• verify/string/string_algorithms.test.cpp

Code

#ifndef M1UNE_STRING_MINIMUM_ROTATION_HPP
#define M1UNE_STRING_MINIMUM_ROTATION_HPP 1

namespace m1une {
namespace string {

// Returns the smallest starting index of a lexicographically minimum cyclic shift.
template <class Sequence>
int minimum_cyclic_shift(const Sequence& sequence) {
    const int size = int(sequence.size());
    if (size == 0) return 0;

    auto less = [&](int left, int right) {
        return sequence[left < size ? left : left - size] <
               sequence[right < size ? right : right - size];
    };

    int answer = 0;
    int start = 0;
    while (start < size) {
        answer = start;
        int scan = start + 1;
        int matched = start;
        while (scan < 2 * size && !less(scan, matched)) {
            if (less(matched, scan)) {
                matched = start;
            } else {
                matched++;
            }
            scan++;
        }

        const int period = scan - matched;
        while (start <= matched) start += period;
    }
    return answer;
}

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_MINIMUM_ROTATION_HPP

#line 1 "string/minimum_rotation.hpp"



namespace m1une {
namespace string {

// Returns the smallest starting index of a lexicographically minimum cyclic shift.
template <class Sequence>
int minimum_cyclic_shift(const Sequence& sequence) {
    const int size = int(sequence.size());
    if (size == 0) return 0;

    auto less = [&](int left, int right) {
        return sequence[left < size ? left : left - size] <
               sequence[right < size ? right : right - size];
    };

    int answer = 0;
    int start = 0;
    while (start < size) {
        answer = start;
        int scan = start + 1;
        int matched = start;
        while (scan < 2 * size && !less(scan, matched)) {
            if (less(matched, scan)) {
                matched = start;
            } else {
                matched++;
            }
            scan++;
        }

        const int period = scan - matched;
        while (start <= matched) start += period;
    }
    return answer;
}

}  // namespace string
}  // namespace m1une

Back to top page