sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#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"); }