Periodic Substring

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int INF = 1e9;

template<typename T> struct rmq {
    vector<T> v;
    int n; static const int b = 30;
    vector<int> mask, t;

    int op(int x, int y) { return v[x] <= v[y] ? x : y; }
    int msb(int x) { return __builtin_clz(1)-__builtin_clz(x); }
    int small(int r, int sz = b) { return r-msb(mask[r]&((1<<sz)-1)); }
    rmq() {}
    rmq(const vector<T>& v_) : v(v_), n(v.size()), mask(n), t(n) {
        for (int i = 0, at = 0; i < n; mask[i++] = at |= 1) {
            at = (at<<1)&((1<<b)-1);
            while (at and op(i-msb(at&-at), i) == i) at ^= at&-at;
        }
        for (int i = 0; i < n/b; i++) t[i] = small(b*i+b-1);
        for (int j = 1; (1<<j) <= n/b; j++) for (int i = 0; i+(1<<j) <= n/b; i++)
            t[n/b*j+i] = op(t[n/b*(j-1)+i], t[n/b*(j-1)+i+(1<<(j-1))]);
    }
    int index_query(int l, int r) {
        if (r-l+1 <= b) return small(r, r-l+1);
        int x = l/b+1, y = r/b-1;
        if (x > y) return op(small(l+b-1), small(r));
        int j = msb(y-x+1);
        int ans = op(small(l+b-1), op(t[n/b*j+x], t[n/b*j+y-(1<<j)+1]));
        return op(ans, small(r));
    }
    T query(int l, int r) { return v[index_query(l, r)]; }
};

vector<int> sort_cyclic_shifts(string const& s) {
  int n = s.size();
  const int alphabet = 256;

  vector<int> p(n), c(n), cnt(max(alphabet, n), 0);
  for (int i = 0; i < n; i++)
    cnt[s[i]]++;
  for (int i = 1; i < alphabet; i++)
    cnt[i] += cnt[i-1];
  for (int i = 0; i < n; i++)
    p[--cnt[s[i]]] = i;
  c[p[0]] = 0;
  int classes = 1;
  for (int i = 1; i < n; i++) {
    if (s[p[i]] != s[p[i-1]])
        classes++;
    c[p[i]] = classes - 1;
  }

  vector<int> pn(n), cn(n);
  for (int h = 0; (1 << h) < n; ++h) {
    for (int i = 0; i < n; ++i) {
      pn[i] = p[i] - (1 << h);
      if (pn[i] < 0)
        pn[i] += n;
    }

    fill(cnt.begin(), cnt.begin() + classes, 0);
    for (int i = 0; i < n; i++)
      cnt[c[pn[i]]]++;
    for (int i = 1; i < classes; i++)
      cnt[i] += cnt[i-1];
    for (int i = n-1; i >= 0; i--)
      p[--cnt[c[pn[i]]]] = pn[i];
    cn[p[0]] = 0;
    classes = 1;
    for (int i = 1; i < n; i++) {
      pair<int, int> cur = {c[p[i]], c[(p[i] + (1 << h)) % n]};
      pair<int, int> prev = {c[p[i-1]], c[(p[i-1] + (1 << h)) % n]};
      if (cur != prev)
        ++classes;
      cn[p[i]] = classes - 1;
    }
    c.swap(cn);
  }

  return p;
}

vector<int> suffix_array_construction(string s) {
  s += "$";
  vector<int> sorted_shifts = sort_cyclic_shifts(s);
  sorted_shifts.erase(sorted_shifts.begin());
  return sorted_shifts;
}

vector<int> lcp_construction(const string &s, const vector<int> &p) {
  int n = s.size();

  vector<int> rank(n, 0);
  for (int i = 0; i < n; ++i) {
    rank[p[i]] = i;
  }

  int k = 0;
  vector<int> lcp(n-1, 0);
  for (int i = 0; i < n; ++i) {
    if (rank[i] == n-1) {
      k = 0;
      continue;
    }

    int j = p[rank[i] + 1];
    while (i + k < n and j + k < n and s[i + k] == s[j + k])
      ++k;
    lcp[rank[i]] = k;
    if (k) --k;
  }

  return lcp;
}

int n;
int ans = -INF;

vector<int> SA, lcp, rnk;
rmq<int> ST;

// dfs na suffix tree
void dfs(int L, int R, int p, pair<int, int> &nearest, set<int> &st) {
  int ext = L != R ? ST.query(L, R-1) : n - SA[L];

  int l = L, r = R;
  if (SA[L]+ext == n) {
    st.insert(SA[L]);
    L++;
  }

  set<int> my_set;
  pair<int, int> my_nearest({-INF, INF});

  while (L <= R) {
    int idx = L != R ? ST.index_query(L, R-1) : -1;
    if (idx == -1 or lcp[idx] != ext) idx = R;

    dfs(L, idx, ext, my_nearest, my_set);

    if (my_set.size() > st.size()) {
      swap(st, my_set);
    }

    int diff = abs(my_nearest.fi - my_nearest.se);
    if (diff < abs(nearest.fi - nearest.se)) {
      nearest = my_nearest;
    }

    for (int x : my_set) {
      st.insert(x);
      auto aux = st.lower_bound(x);
      auto it = aux;

      if (it != prev(st.end())) {
        int nxt = *next(it);
        int diff = abs(x - nxt);
        if (diff < abs(nearest.fi - nearest.se)) {
          nearest = {x, nxt};
        }
      }

      it = aux;
      if (it != st.begin()) {
        int prv = *prev(it);
        int diff = abs(x - prv);
        if (diff < abs(nearest.fi - nearest.se)) {
          nearest = {x, prv};
        }
      }
    }

    my_set.clear();
    my_nearest = {-INF, INF};
    L = idx+1;
  }

  int ll = nearest.fi, rr = nearest.se;
  if (ll > rr) swap(ll, rr);
  if (l != r and ll != rr) {
    ans = max(ans,
      ST.query(l, r-1) / (rr - ll) + 1
    );
  }
  // cout << l << ' ' << r << " -> " << ll << ' ' << rr << ' ' <<
  //   (ST.query(l, r-1) / (rr - ll) + 1) <<  '\n';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);

  string s; cin >> s;
  n = s.size();
  rnk.assign(n, 0);

  SA = suffix_array_construction(s);
  lcp = lcp_construction(s, SA);

  for (int i = 0; i < (int)SA.size(); ++i) {
    // cout << i << ' ' << SA[i] << ' ' << s.substr(SA[i]) << '\n';
    rnk[SA[i]] = i;
  }

  // for (int i = 0; i < (int)lcp.size(); ++i) {
  //   cout << lcp[i] << '\n';
  // }

  ST = rmq<int>(lcp);

  set<int> my_set;
  pair<int, int> nearest({-INF, INF});
  dfs(0, n-1, 0, nearest, my_set);

  // for (int x : my_set) {
  //   cout << x << ' ';
  // } cout << '\n';

  // cout << nearest.fi << ' ' << nearest.se << '\n';

  cout << ans << '\n';
}
/*
ababba

0. a
1. aba
2. abba
3. ba
4. babba
5. bba

*/