test/yosupo/lyndon_factorization.test.cpp

• View this file on GitHub
• Last update: 2024-01-07 22:05:53+09:00
• Problem: https://judge.yosupo.jp/problem/lyndon_factorization

Depends on

• Lyndon Factorization (string/lyndon_factorization.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/lyndon_factorization"

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

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string S;
    cin >> S;
    auto res = lyndon_factorization(S);
    for (int i = 0; i < (int)res.size(); ++i)
        cout << res[i] << (i < (int)res.size() ? " " : "\n");
}

#line 1 "test/yosupo/lyndon_factorization.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/lyndon_factorization"

#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;
}
#line 4 "test/yosupo/lyndon_factorization.test.cpp"

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    string S;
    cin >> S;
    auto res = lyndon_factorization(S);
    for (int i = 0; i < (int)res.size(); ++i)
        cout << res[i] << (i < (int)res.size() ? " " : "\n");
}

Back to top page