Lyndon Factorization
(string/lyndon_factorization.hpp)

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

Description

Lyndon word とは，その任意の proper suffix よりも辞書順で真に小さいような文字列である．

任意の文字列は，単調非増加な Lyndon word の結合として一意的に分解される．この分解を Lyndon factorization という．

Operations

• vector<int> lyndon_factorization(string s)
  • 文字列 $s$ を Lyndon factorization したときの，各 Lyndon word の最初の index を返す
  • 時間計算量: $O(n)$

Reference

• Lyndon factorization - Algorithms for Competitive Programming

Verified with

• test/yosupo/lyndon_factorization.test.cpp

Code

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

std::vector<int> lyndon_factorization(const std::string& s) {
    const int n = s.size();
    std::vector<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;
        }
        while (i <= k) {
            res.push_back(i);
            i += j - k;
        }
    }
    res.push_back(n);
    return res;
}

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

std::vector<int> lyndon_factorization(const std::string& s) {
    const int n = s.size();
    std::vector<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;
        }
        while (i <= k) {
            res.push_back(i);
            i += j - k;
        }
    }
    res.push_back(n);
    return res;
}

Back to top page