string/run_enumerate.hpp

• View this file on GitHub
• Last update: 2023-11-15 20:12:22+09:00
• Include: #include "string/run_enumerate.hpp"

Depends on

• string/zalgorithm.hpp

Verified with

• test/library_checker/string/run_enumerate.test.cpp
• test/library_checker/string/run_enumerate_vec.test.cpp

Code

#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 1 "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;
}

Back to top page