This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub maspypy/library
#include "string/run_enumerate.hpp"
#include "string/zalgorithm.hpp" // (period, l, r) // 極大, つまり S[l:r] は周期 p (ただし r-l >= 2p) を持つが、S[l-1:r], S[l:r+1] // はそうではない // 高々 n 個以下 // sum of (r-l)/p = O(n) template <typename STRING> vc<tuple<int, int, int>> run_enumerate(const STRING& S) { ll N = len(S); using T = tuple<int, int, int>; using P = pair<int, int>; vc<vc<P>> by_p(N + 1); auto solve_sub = [&](STRING& left, STRING& right) -> vc<T> { vc<T> res; int n = len(left), m = len(right); auto S = left, T = right; reverse(all(S)); T.insert(T.end(), all(left)); T.insert(T.end(), all(right)); auto ZS = zalgorithm(S), ZT = zalgorithm(T); FOR3(p, 1, n + 1) { int a = (p == n ? p : min(ZS[p] + int(p), n)); int b = min(ZT[n + m - p], m); if (a + b < 2 * p) continue; res.eb(p, a, b); } return res; }; vc<P> st = {{0, N}}; while (!st.empty()) { auto [L, R] = st.back(); st.pop_back(); if (R - L <= 1) continue; int M = (L + R) / 2; st.eb(L, M), st.eb(M, R); STRING SL = {S.begin() + L, S.begin() + M}; STRING SR = {S.begin() + M, S.begin() + R}; { auto sub_res = solve_sub(SL, SR); for (auto&& [p, a, b]: sub_res) by_p[p].eb(M - a, M + b); } { reverse(all(SL)), reverse(all(SR)); auto sub_res = solve_sub(SR, SL); for (auto&& [p, a, b]: sub_res) by_p[p].eb(M - b, M + a); } } vc<T> res; set<P> done; FOR(p, len(by_p)) { auto& LR = by_p[p]; sort(all(LR), [](auto& x, auto& y) { return P(x.fi, -x.se) < P(y.fi, -y.se); }); int r = -1; for (auto&& lr: LR) { if (chmax(r, lr.se) && !done.count(lr)) { done.insert(lr); res.eb(p, lr.fi, lr.se); } } } return res; }
#line 2 "string/zalgorithm.hpp" template <typename STRING> // string, vector どちらでも vector<int> zalgorithm(const STRING& s) { int n = int(s.size()); if (n == 0) return {}; vector<int> z(n); z[0] = 0; for (int i = 1, j = 0; i < n; i++) { int& k = z[i]; k = (j + z[j] <= i) ? 0 : min(j + z[j] - i, z[i - j]); while (i + k < n && s[k] == s[i + k]) k++; if (j + z[j] < i + z[i]) j = i; } z[0] = n; return z; } #line 2 "string/run_enumerate.hpp" // (period, l, r) // 極大, つまり S[l:r] は周期 p (ただし r-l >= 2p) を持つが、S[l-1:r], S[l:r+1] // はそうではない // 高々 n 個以下 // sum of (r-l)/p = O(n) template <typename STRING> vc<tuple<int, int, int>> run_enumerate(const STRING& S) { ll N = len(S); using T = tuple<int, int, int>; using P = pair<int, int>; vc<vc<P>> by_p(N + 1); auto solve_sub = [&](STRING& left, STRING& right) -> vc<T> { vc<T> res; int n = len(left), m = len(right); auto S = left, T = right; reverse(all(S)); T.insert(T.end(), all(left)); T.insert(T.end(), all(right)); auto ZS = zalgorithm(S), ZT = zalgorithm(T); FOR3(p, 1, n + 1) { int a = (p == n ? p : min(ZS[p] + int(p), n)); int b = min(ZT[n + m - p], m); if (a + b < 2 * p) continue; res.eb(p, a, b); } return res; }; vc<P> st = {{0, N}}; while (!st.empty()) { auto [L, R] = st.back(); st.pop_back(); if (R - L <= 1) continue; int M = (L + R) / 2; st.eb(L, M), st.eb(M, R); STRING SL = {S.begin() + L, S.begin() + M}; STRING SR = {S.begin() + M, S.begin() + R}; { auto sub_res = solve_sub(SL, SR); for (auto&& [p, a, b]: sub_res) by_p[p].eb(M - a, M + b); } { reverse(all(SL)), reverse(all(SR)); auto sub_res = solve_sub(SR, SL); for (auto&& [p, a, b]: sub_res) by_p[p].eb(M - b, M + a); } } vc<T> res; set<P> done; FOR(p, len(by_p)) { auto& LR = by_p[p]; sort(all(LR), [](auto& x, auto& y) { return P(x.fi, -x.se) < P(y.fi, -y.se); }); int r = -1; for (auto&& lr: LR) { if (chmax(r, lr.se) && !done.count(lr)) { done.insert(lr); res.eb(p, lr.fi, lr.se); } } } return res; }