This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "strings/lyndon.hpp"
It computes the following problems efficiently:
#pragma once vector<string> duval(string const& s) { int n = s.size(); int i = 0; vector<string> factorization; while (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) { factorization.push_back(s.substr(i, j - k)); i += j - k; } } return factorization; } string min_cyclic_string(string s) { s += s; int n = s.size(); int i = 0, ans = 0; while (i < n / 2) { ans = i; 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) i += j - k; } return s.substr(ans, n / 2); }
#line 2 "strings/lyndon.hpp" vector<string> duval(string const& s) { int n = s.size(); int i = 0; vector<string> factorization; while (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) { factorization.push_back(s.substr(i, j - k)); i += j - k; } } return factorization; } string min_cyclic_string(string s) { s += s; int n = s.size(); int i = 0, ans = 0; while (i < n / 2) { ans = i; 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) i += j - k; } return s.substr(ans, n / 2); }