Lyndon分解(Lyndon Factorization)
(string/lyndon_factorization.cpp)

• View this file on GitHub
• Last update: 2026-03-12 00:49:33+09:00

説明

文字列を Lyndon word の非増加列に一意に分解する。 Duval algorithm により $O(|s|)$。

できること

• vector<pair<int, int>> lyndon_factorization(const string& s) 各因子の半開区間 [l, r) を順に返す。空文字列なら空 vector を返す

使い方

返り値の各区間を s.substr(l, r - l) として取り出せる。

auto segs = lyndon_factorization(s);
for (auto &&[l, r] : segs) {
    string t = s.substr(l, r - l);
}

実装上の補足

• 返る因子列は辞書順で単調非増加
• 区間で返すので、追加の文字列コピーなしで他の処理に渡せる

Verified with

• test/yosupo_lyndon_factorization.test.cpp

Code

using namespace std;

vector<pair<int, int>> lyndon_factorization(const string &s) {
    int n = (int)s.size();
    vector<pair<int, int>> res;
    for (int i = 0; i < n;) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j]) k = i;
            else ++k;
            ++j;
        }
        int len = j - k;
        while (i <= k) {
            res.emplace_back(i, i + len);
            i += len;
        }
    }
    return res;
}

/**
 * @brief Lyndon分解(Lyndon Factorization)
 */

#line 1 "string/lyndon_factorization.cpp"
using namespace std;

vector<pair<int, int>> lyndon_factorization(const string &s) {
    int n = (int)s.size();
    vector<pair<int, int>> res;
    for (int i = 0; i < n;) {
        int j = i + 1, k = i;
        while (j < n && s[k] <= s[j]) {
            if (s[k] < s[j]) k = i;
            else ++k;
            ++j;
        }
        int len = j - k;
        while (i <= k) {
            res.emplace_back(i, i + len);
            i += len;
        }
    }
    return res;
}

/**
 * @brief Lyndon分解(Lyndon Factorization)
 */

Back to top page