This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub hitonanode/cplib-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/lyndon_factorization" #include "../lyndon.hpp" #include <iostream> #include <string> using namespace std; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); string S; cin >> S; auto ret = lyndon_factorization(S); for (auto [l, len] : ret) cout << l << ' '; cout << S.size() << '\n'; }
#line 1 "string/test/lyndon.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/lyndon_factorization" #line 2 "string/lyndon.hpp" #include <algorithm> #include <cassert> #include <functional> #include <string> #include <tuple> #include <utility> #include <vector> // CUT begin // Lyndon factorization based on Duval's algorithm // **NOT VERIFIED YET** // Reference: // [1] K. T. Chen, R. H. Fox, R. C. Lyndon, // "Free Differential Calculus, IV. The Quotient Groups of the Lower Central Series," // Annals of Mathematics, 68(1), 81-95, 1958. // [2] J. P. Duval, "Factorizing words over an ordered alphabet," // Journal of Algorithms, 4(4), 363-381, 1983. // - https://cp-algorithms.com/string/lyndon_factorization.html // - https://qiita.com/nakashi18/items/66882bd6e0127174267a template <typename T> std::vector<std::pair<int, int>> lyndon_factorization(const std::vector<T> &S) { const int N = S.size(); std::vector<std::pair<int, int>> ret; for (int l = 0; l < N;) { int i = l, j = i + 1; while (j < N and S[i] <= S[j]) i = (S[i] == S[j] ? i + 1 : l), j++; int n = (j - l) / (j - i); for (int t = 0; t < n; t++) ret.emplace_back(l, j - i), l += j - i; } return ret; } std::vector<std::pair<int, int>> lyndon_factorization(const std::string &s) { const int N = int(s.size()); std::vector<int> v(N); for (int i = 0; i < N; i++) v[i] = s[i]; return lyndon_factorization<int>(v); } // Compute the longest Lyndon prefix for each suffix s[i:N] // (Our implementation is $O(N \cdot (complexity of lcplen()))$) // Example: // - `teletelepathy` -> [1,4,1,2,1,4,1,2,1,4,1,2,1] // Reference: // [1] H. Bannai et al., "The "Runs" Theorem," // SIAM Journal on Computing, 46(5), 1501-1514, 2017. template <typename String, typename LCPLENCallable> std::vector<int> longest_lyndon_prefixes(const String &s, const LCPLENCallable &lcp) { const int N = s.size(); std::vector<std::pair<int, int>> st{{N, N}}; std::vector<int> ret(N); for (int i = N - 1, j = i; i >= 0; i--, j = i) { while (st.size() > 1) { int iv = st.back().first, jv = st.back().second; int l = lcp.lcplen(i, iv); if (!(iv + l < N and s[i + l] < s[iv + l])) break; j = jv; st.pop_back(); } st.emplace_back(i, j); ret[i] = j - i + 1; } return ret; } // Compute all runs in given string // Complexity: $O(N \cdot (complexity of lcplen()))$ in this implementation // (Theoretically $O(N)$ achievable) // N = 2e5 -> ~120 ms // Reference: // [1] H. Bannai et al., "The "Runs" Theorem," // SIAM Journal on Computing, 46(5), 1501-1514, 2017. template <typename LCPLENCallable, typename String> std::vector<std::tuple<int, int, int>> run_enumerate(String s) { if (s.empty()) return {}; LCPLENCallable lcp(s); std::reverse(s.begin(), s.end()); LCPLENCallable revlcp(s); std::reverse(s.begin(), s.end()); auto t = s; auto lo = *std::min_element(s.begin(), s.end()), hi = *std::max_element(s.begin(), s.end()); for (auto &c : t) c = hi - (c - lo); auto l1 = longest_lyndon_prefixes(s, lcp), l2 = longest_lyndon_prefixes(t, lcp); int N = s.size(); std::vector<std::tuple<int, int, int>> ret; for (int i = 0; i < N; i++) { int j = i + l1[i], L = i - revlcp.lcplen(N - i, N - j), R = j + lcp.lcplen(i, j); if (R - L >= (j - i) * 2) ret.emplace_back(j - i, L, R); if (l1[i] != l2[i]) { j = i + l2[i], L = i - revlcp.lcplen(N - i, N - j), R = j + lcp.lcplen(i, j); if (R - L >= (j - i) * 2) ret.emplace_back(j - i, L, R); } } std::sort(ret.begin(), ret.end()); ret.erase(std::unique(ret.begin(), ret.end()), ret.end()); return ret; } // Enumerate Lyndon words up to length n in lexical order // https://github.com/bqi343/USACO/blob/master/Implementations/content/combinatorial%20(11.2)/DeBruijnSeq.h // Example: k=2, n=4 => [[0,],[0,0,0,1,],[0,0,1,],[0,0,1,1,],[0,1,],[0,1,1,],[0,1,1,1,],[1,],] // Verified: https://codeforces.com/gym/102001/problem/C / https://codeforces.com/gym/100162/problem/G std::vector<std::vector<int>> enumerate_lyndon_words(int k, int n) { assert(k > 0); assert(n > 0); std::vector<std::vector<int>> ret; std::vector<int> aux(n + 1); std::function<void(int, int)> gen = [&](int t, int p) { // t: current length // p: current min cycle length if (t == n) { std::vector<int> tmp(aux.begin() + 1, aux.begin() + p + 1); ret.push_back(std::move(tmp)); } else { ++t; aux[t] = aux[t - p]; gen(t, p); while (++aux[t] < k) gen(t, t); } }; gen(0, 1); return ret; } #line 3 "string/test/lyndon.test.cpp" #include <iostream> #line 6 "string/test/lyndon.test.cpp" using namespace std; int main() { cin.tie(nullptr); ios_base::sync_with_stdio(false); string S; cin >> S; auto ret = lyndon_factorization(S); for (auto [l, len] : ret) cout << l << ' '; cout << S.size() << '\n'; }