#include "string/run-enumerate.hpp"
#pragma once #include <algorithm> #include <set> #include <utility> #include <vector> using namespace std; #include "z-algorithm.hpp" // (p, l, r) : S[l, r) は周期 p かつ極大 // sum_{(p,l,r)} 1 <= n // sum_{(p,l,r)} (r-l)/p <= 3n // sum_{(p,l,r)} (r-l+1-2*p) = O(n log n) template <typename C> vector<tuple<int, int, int>> run_enumerate(const C& S) { int N = S.size(); using T = tuple<int, int, int>; vector<vector<pair<int, int>>> by_p(N + 1); auto solve_sub = [&](const C& l, const C& r) { vector<T> res; int n = l.size(), m = r.size(); C s = l, t = r; t.insert(end(t), begin(l), end(l)); t.insert(end(t), begin(r), end(r)); reverse(begin(s), end(s)); auto ZS = z_algorithm(s), ZT = z_algorithm(t); for (int p = 1; p <= n; p++) { int a = p == n ? p : min(ZS[p] + p, n); int b = min(ZT[n + m - p], m); if (a + b < 2 * p) continue; res.emplace_back(p, a, b); } return res; }; auto dfs = [&](auto rc, int L, int R) -> void { if (R - L <= 1) return; int M = (L + R) / 2; rc(rc, L, M), rc(rc, M, R); C SL{begin(S) + L, begin(S) + M}; C SR{begin(S) + M, begin(S) + R}; auto sub_res1 = solve_sub(SL, SR); for (auto& [p, a, b] : sub_res1) by_p[p].emplace_back(M - a, M + b); reverse(begin(SL), end(SL)); reverse(begin(SR), end(SR)); auto sub_res2 = solve_sub(SR, SL); for (auto& [p, a, b] : sub_res2) by_p[p].emplace_back(M - b, M + a); }; dfs(dfs, 0, N); vector<T> res; set<pair<int, int>> done; for (int p = 0; p <= N; p++) { auto& LR = by_p[p]; sort(begin(LR), end(LR), [](auto& x, auto& y) { if (x.first == y.first) return x.second > y.second; return x.first < y.first; }); int r = -1; for (auto& lr : LR) { if (r >= lr.second) continue; r = lr.second; if (!done.count(lr)) { done.insert(lr); res.emplace_back(p, lr.first, lr.second); } } } return res; }
#line 2 "string/run-enumerate.hpp" #include <algorithm> #include <set> #include <utility> #include <vector> using namespace std; #line 2 "string/z-algorithm.hpp" template <typename Container> vector<int> z_algorithm(const Container& s) { int n = s.size(); if(n == 0) return {}; vector<int> a(n); a[0] = n; int i = 1, j = 0; while (i < n) { while (i + j < n && s[j] == s[i + j]) j++; a[i] = j; if (j == 0) { i++; continue; } int k = 1; while (i + k < n && k + a[k] < j) a[i + k] = a[k], k++; i += k, j -= k; } return a; } /** * @brief Z algorithm */ #line 10 "string/run-enumerate.hpp" // (p, l, r) : S[l, r) は周期 p かつ極大 // sum_{(p,l,r)} 1 <= n // sum_{(p,l,r)} (r-l)/p <= 3n // sum_{(p,l,r)} (r-l+1-2*p) = O(n log n) template <typename C> vector<tuple<int, int, int>> run_enumerate(const C& S) { int N = S.size(); using T = tuple<int, int, int>; vector<vector<pair<int, int>>> by_p(N + 1); auto solve_sub = [&](const C& l, const C& r) { vector<T> res; int n = l.size(), m = r.size(); C s = l, t = r; t.insert(end(t), begin(l), end(l)); t.insert(end(t), begin(r), end(r)); reverse(begin(s), end(s)); auto ZS = z_algorithm(s), ZT = z_algorithm(t); for (int p = 1; p <= n; p++) { int a = p == n ? p : min(ZS[p] + p, n); int b = min(ZT[n + m - p], m); if (a + b < 2 * p) continue; res.emplace_back(p, a, b); } return res; }; auto dfs = [&](auto rc, int L, int R) -> void { if (R - L <= 1) return; int M = (L + R) / 2; rc(rc, L, M), rc(rc, M, R); C SL{begin(S) + L, begin(S) + M}; C SR{begin(S) + M, begin(S) + R}; auto sub_res1 = solve_sub(SL, SR); for (auto& [p, a, b] : sub_res1) by_p[p].emplace_back(M - a, M + b); reverse(begin(SL), end(SL)); reverse(begin(SR), end(SR)); auto sub_res2 = solve_sub(SR, SL); for (auto& [p, a, b] : sub_res2) by_p[p].emplace_back(M - b, M + a); }; dfs(dfs, 0, N); vector<T> res; set<pair<int, int>> done; for (int p = 0; p <= N; p++) { auto& LR = by_p[p]; sort(begin(LR), end(LR), [](auto& x, auto& y) { if (x.first == y.first) return x.second > y.second; return x.first < y.first; }); int r = -1; for (auto& lr : LR) { if (r >= lr.second) continue; r = lr.second; if (!done.count(lr)) { done.insert(lr); res.emplace_back(p, lr.first, lr.second); } } } return res; }