string/periods.hpp

View this file on GitHub
Last update: 2026-09-14 17:13:23+09:00
Include: #include "string/periods.hpp"

Depends on

string/z_algorithm.hpp

Code

#include "string/z_algorithm.hpp"

template <typename STRING>
vc<int> periods(const STRING& S, bool is_divisor) {
  int N = len(S);
  auto Z = z_algorithm(S);
  vc<int> res;
  FOR(p, 1, N + 1) {
    if (is_divisor && (N % p != 0)) continue;
    if (p == N || Z[p] == N - p) res.eb(p);
  }
  return res;
}

#line 1 "string/z_algorithm.hpp"

template <typename STRING>  // string, vector どちらでも
vector<int> z_algorithm(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/periods.hpp"

template <typename STRING>
vc<int> periods(const STRING& S, bool is_divisor) {
  int N = len(S);
  auto Z = z_algorithm(S);
  vc<int> res;
  FOR(p, 1, N + 1) {
    if (is_divisor && (N % p != 0)) continue;
    if (p == N || Z[p] == N - p) res.eb(p);
  }
  return res;
}