test/library_checker/string/lyndon_factorization.test.cpp

• View this file on GitHub
• Last update: 2024-10-31 22:40:32+09:00
• Problem: https://judge.yosupo.jp/problem/lyndon_factorization

Depends on

• Lyndon Factorization (lib/string/lyndon_factorization.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lyndon_factorization"
#include <bits/stdc++.h>
using namespace std;

#include "../../../lib/string/lyndon_factorization.hpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; cin >> s;
    auto ans = lyndon_factorization(s);
    int len = ans.size();
    for(int i = 0; i < len; i++){
        if(i >= 1) cout << ' ';
        cout << ans[i];
    }
}

#line 1 "test/library_checker/string/lyndon_factorization.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lyndon_factorization"
#include <bits/stdc++.h>
using namespace std;

#line 2 "lib/string/lyndon_factorization.hpp"

/**
 * @brief Lyndon Factorization
 * @docs docs/string/lyndon_factorization.md
 * @see https://qiita.com/nakashi18/items/66882bd6e0127174267a
 */

template <typename T>
vector<int> lyndon_factorization(const T &s){
    int n = s.size();
    vector<int> ans = {0};
    int l = 0;
    while(l < n){
        // [l, ?) の最長の Lyndon 文字列を見つける
        int i = l, j = l + 1;
        while(s[i] <= s[j] && j < n){
            if(s[i] == s[j]) i++;
            else i = l;
            j++;
        }
        // (j - i) が周期で、[l, j) がその周期の繰り返し
        int repet = (j - l) / (j - i);
        for(int d = 0; d < repet; d++){
            l += j - i;
            ans.push_back(l);
        }
    }
    return ans;
}
#line 6 "test/library_checker/string/lyndon_factorization.test.cpp"

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s; cin >> s;
    auto ans = lyndon_factorization(s);
    int len = ans.size();
    for(int i = 0; i < len; i++){
        if(i >= 1) cout << ' ';
        cout << ans[i];
    }
}

Back to top page