Lyndon Factorization
(string/lyndon_factorization.hpp)

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

Overview

The Lyndon factorization decomposes a sequence into a lexicographically non-increasing sequence of Lyndon words. It is useful in string ordering, minimal rotations, runs, and suffix-related algorithms.

The implementation uses Duval’s algorithm. Including this header also includes minimum_rotation.hpp for compatibility, so minimum_cyclic_shift remains available to existing users.

All functions are generic over indexable sequences such as std::string and std::vector<int>. Elements are compared with operator<.

Functions

Function	Description	Complexity
vector<int> lyndon_factor_boundaries(const Sequence& sequence)	Returns boundaries 0 = a[0] < a[1] < ... < a[k] = N.	$O(N)$
vector<pair<int, int>> lyndon_factorization(const Sequence& sequence)	Returns the factor intervals as half-open ranges [left, right).	$O(N)$
int minimum_cyclic_shift(const Sequence& sequence)	Compatibility re-export from minimum_rotation.hpp; returns the earliest minimum cyclic shift.	$O(N)$

For an empty sequence, lyndon_factor_boundaries returns {0}, lyndon_factorization returns an empty vector, and minimum_cyclic_shift returns 0.

Example

#include "string/lyndon_factorization.hpp"

#include <iostream>
#include <string>

int main() {
    std::string text = "banana";
    auto factors = m1une::string::lyndon_factorization(text);

    for (auto [left, right] : factors) {
        std::cout << text.substr(left, right - left) << "\n";
    }

    int start = m1une::string::minimum_cyclic_shift(text);
    std::cout << text.substr(start) + text.substr(0, start) << "\n";
}

Depends on

• Minimum Rotation (string/minimum_rotation.hpp)

Required by

• String Algorithms Bundle (string/all.hpp)

Verified with

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

Code

#ifndef M1UNE_STRING_LYNDON_FACTORIZATION_HPP
#define M1UNE_STRING_LYNDON_FACTORIZATION_HPP 1

#include <utility>
#include <vector>

#include "minimum_rotation.hpp"

namespace m1une {
namespace string {

// Returns boundaries 0 = a[0] < a[1] < ... < a[k] = sequence.size()
// of the Lyndon factorization.
template <class Sequence>
std::vector<int> lyndon_factor_boundaries(const Sequence& sequence) {
    int n = int(sequence.size());
    std::vector<int> boundaries;
    boundaries.push_back(0);

    int i = 0;
    while (i < n) {
        int j = i + 1;
        int k = i;
        while (j < n && !(sequence[j] < sequence[k])) {
            if (sequence[k] < sequence[j]) {
                k = i;
            } else {
                k++;
            }
            j++;
        }

        int length = j - k;
        while (i <= k) {
            i += length;
            boundaries.push_back(i);
        }
    }
    return boundaries;
}

// Returns half-open intervals [left, right) of the Lyndon factorization.
template <class Sequence>
std::vector<std::pair<int, int>> lyndon_factorization(const Sequence& sequence) {
    std::vector<int> boundaries = lyndon_factor_boundaries(sequence);
    std::vector<std::pair<int, int>> factors;
    factors.reserve(boundaries.size() - 1);
    for (int i = 0; i + 1 < int(boundaries.size()); i++) {
        factors.emplace_back(boundaries[i], boundaries[i + 1]);
    }
    return factors;
}

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_LYNDON_FACTORIZATION_HPP

#line 1 "string/lyndon_factorization.hpp"



#include <utility>
#include <vector>

#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


#line 8 "string/lyndon_factorization.hpp"

namespace m1une {
namespace string {

// Returns boundaries 0 = a[0] < a[1] < ... < a[k] = sequence.size()
// of the Lyndon factorization.
template <class Sequence>
std::vector<int> lyndon_factor_boundaries(const Sequence& sequence) {
    int n = int(sequence.size());
    std::vector<int> boundaries;
    boundaries.push_back(0);

    int i = 0;
    while (i < n) {
        int j = i + 1;
        int k = i;
        while (j < n && !(sequence[j] < sequence[k])) {
            if (sequence[k] < sequence[j]) {
                k = i;
            } else {
                k++;
            }
            j++;
        }

        int length = j - k;
        while (i <= k) {
            i += length;
            boundaries.push_back(i);
        }
    }
    return boundaries;
}

// Returns half-open intervals [left, right) of the Lyndon factorization.
template <class Sequence>
std::vector<std::pair<int, int>> lyndon_factorization(const Sequence& sequence) {
    std::vector<int> boundaries = lyndon_factor_boundaries(sequence);
    std::vector<std::pair<int, int>> factors;
    factors.reserve(boundaries.size() - 1);
    for (int i = 0; i + 1 < int(boundaries.size()); i++) {
        factors.emplace_back(boundaries[i], boundaries[i + 1]);
    }
    return factors;
}

}  // namespace string
}  // namespace m1une

Back to top page