SP687 REPEATS - Repeats

· · 题解

XXII. SP687 REPEATS - Repeats

借用优秀的拆分的套路，直接枚举循环节长度 L，每相邻 L 个位置放置一个关键点。容易发现，若某个长度为 L 的子串连续出现 k 次，则它恰好跨过 k 个关键点。

Sol 1：显然答案满足可二分性。二分 k，考虑所有连续 k 个关键点 p, p + L, \cdots, p + (k - 1)L，若这些位置对应的所有后缀的 LCP（长度 tor）加上它们对应的所有前缀的 LCS（长度 tol）减去同时覆盖的关键点后覆盖的长度不小于 L，即 tor + tol - 1 \geq L，说明出现 (k, L) - repeat。从小到大扫过所有连续的 k 个关键点，用单调队列维护当前窗口内关键点排名的最大值和最小值方便求 LCP & LCS。因为关键点总数为调和级数的 \mathcal{O}(n\ln n)，所以时间复杂度 \mathcal{O}(n\log ^ 2 n)。

Sol 2：Sol 1 太不优美了。L 固定时，称关键点区间 [l, r] 表示关键点为 p_l, p_{l + 1}, \cdots, p_r(p_i = p_{i - 1} + L) 是优秀的，当且仅当它对应的 tor + tol - 1 不大于 L，出现 (r - l + 1, L) - repeat。显然若 [l, r] 优秀则其任何子区间优秀，推得 r 增加时最左合法左端点单调不降，满足 two-pointers 的条件。双指针替代二分，时间复杂度 \mathcal{O}(n\log n)。

Sol 3：Sol 2 仍不够优美。根据 border 论最经典结论，s 有长 L 的 period 当且仅当 s 有长 n - L 的 border，即 s[1, n - L] = s[L + 1, n]。考虑相邻关键点 p 和 q = p + L，求出 tor = |lcp(suf_p, suf_q)| 和 tol = |lcs(pre_p, pre_q)|，说明 suf_{p - tol + 1} 和 suf_{q - tol + 1} 有长为 tol + tor - 1 的 LCP。为使得覆盖 p, q 的 (k, L) - repeat 最长，它会从 p - tol + 1 开始，满足有 border s[p - tol + 1, p + tor - 1] = s[q - tol + 1, q + tor - 1]。容易发现对应出现次数 k 等于 \dfrac {(q + tor - 1) - (p - tol + 1) + 1} L 即 \dfrac {tol + tor - 1} L 下取整后加 1。所有相邻两个 p, q 的该式最大值即为所求。时间复杂度仍为线性对数，但代码好写很多。

#include <bits/stdc++.h>
using namespace std;
constexpr int K = 16;
constexpr int N = 5e4 + 5;
int n, lg[N];
char s[N];
struct SA {
  int sa[N], rk[N], ork[N], buc[N], id[N], mi[K][N];
  bool cmp(int a, int b, int w) {return ork[a] == ork[b] && ork[a + w] == ork[b + w];}
  void build(char *s) {
    int m = 1 << 7, p = 0;
    memset(buc, 0, sizeof(buc));
    memset(rk, 0, sizeof(rk));
    for(int i = 1; i <= n; i++) buc[rk[i] = s[i]]++;
    for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
    for(int i = n; i; i--) sa[buc[rk[i]]--] = i;
    for(int w = 1; ; w <<= 1, m = p, p = 0) {
      for(int i = n - w + 1; i <= n; i++) id[++p] = i;
      for(int i = 1; i <= n; i++) if(sa[i] > w) id[++p] = sa[i] - w;
      memset(buc, 0, sizeof(buc));
      memcpy(ork, rk, sizeof(rk));
      p = 0;
      for(int i = 1; i <= n; i++) buc[rk[id[i]]]++;
      for(int i = 1; i <= m; i++) buc[i] += buc[i - 1];
      for(int i = n; i; i--) sa[buc[rk[id[i]]]--] = id[i];
      for(int i = 1; i <= n; i++) rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
      if(p == n) break;
    }
    for(int i = 1, k = 0; i <= n; i++) {
      if(k) k--;
      while(s[i + k] == s[sa[rk[i] - 1] + k]) k++;
      mi[0][rk[i]] = k;
    }
    for(int i = 1; i <= lg[n]; i++)
      for(int j = 1; j + (1 << i) - 1 <= n; j++)
        mi[i][j] = min(mi[i - 1][j], mi[i - 1][j + (1 << i - 1)]);
  }
  int lcp(int i, int j) {
    if((i = rk[i]) > (j = rk[j])) swap(i, j);
    int d = lg[j - (i++)];
    return min(mi[d][i], mi[d][j - (1 << d) + 1]);
  }
} sa, rev;
void solve() {
  scanf("%d", &n);
  for(int i = 1; i <= n; i++) {
    s[i] = getchar();
    while(!isalpha(s[i])) s[i] = getchar();
  }
  s[n + 1] = 0;
  sa.build(s);
  reverse(s + 1, s + n + 1);
  rev.build(s);
  int ans = 1;
  for(int L = 1; L <= n; L++)
    for(int p = L, q = L + L; q <= n; p += L, q += L) {
      int r = sa.lcp(p, q), l = rev.lcp(n - q + 1, n - p + 1);
      ans = max(ans, (l + r - 1) / L + 1);
    }
  cout << ans << endl;
}
int main() {
#ifdef ALEX_WEI
  freopen("1.in", "r", stdin);
  freopen("1.out", "w", stdout);
#endif
  for(int i = 2; i < N; i++) lg[i] = lg[i >> 1] + 1;
  int T;
  cin >> T;
  while(T--) solve();
  return 0;
}
/*
2022/6/16
start coding at 18:58
finish debugging at 19:23
*/