P3975 [TJOI2015]弦论

P3975 [TJOI2015]弦论 后缀数组与后缀自动机的拓展应用（磕了一天的题）

题目描述

给定一个字符串 $s$ ，求排名为 $k$ 的子串，分两种情况：

1. 本质相同，位置不同算 $1$ 种。
2. 本质相同，位置不同算 多 种。

题目正解

$SA/SAM$

题目思路 - $SA$

对于 $SA$ 来讲， $1$ 类相对来将好解一些。对于一个后缀 $x$，比他小的所有子串的个数为：

$$\sum_{i = 1}^{x - 1} n - sa[i] + 1 - height[i]$$

这个东西理解起来就是，你把所有的后缀按照 $rk$ 排成一列，那么对于每个后缀，他能进行的贡献即为 $s[sa[i]\sim sa[i] + height[i]], s[sa[i]\sim sa[i] + height[i] + 1], \cdots, s[sa[i]\sim n]$ 。原因就是对于它和上一段的 $lcp$ ，一定已经在上一段或更早的时候被统计到了。所以可以直接线性扫一遍直到排名刚好为 $k$。

时间复杂度：$O(n)$

$2$ 类相对来说困难一些。因为对于它和后面的后缀的 $lcp$，没有办法当前串统计到。

但是，正难可以反，我们可以发现，给定一个知道起始位置为 $p$ 和长度 $w$ 的串，求他的排名相对来讲简单一些。$rk$ 在它前面的后缀，对答案的贡献为 $\sum n - sa[i] + 1$ （因为本质不同算多个，所以不去要减 $height$）。对于它后面的串，对答案的贡献为 $\sum\min(w, lcp(p, i))$ 后面的 $lcp$ 只需要对 $height$ 预处理 $ST$ 表就能做到 $O(1)$ 查询。最终的式子为：

$$\sum_{i = 1}^{p - 1} (n - sa[i] + 1) + \min(w, n - sa[p] + 1) + \sum_{i = p + 1}^n\min(w, \min_{j = i + 1}^p height[j])$$

现在的关键就是如何求 $p$ 和 $w$ ，做法就是二分情况 $1$ 下的排名。单调性显然。

所以整个过程就是 二分排名（情况 $1$） $\to$ 求出对应的子串 $\to$ 求出排名（情况 $2$），比对。 最终答案要的是 $rk \ge k$ 的最小子串。

时间复杂度：$O(nlogn)$ 表现略差，洛谷数据跑了 $7.3s^+$ 。（可能与我常数大有密切联系）

题目代码 - $SA$

代码

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO  // namespace IO
using namespace IO;
const int Maxn = 5e5 + 10;
using namespace std;

char s[Maxn];
int sa[Maxn], rk[Maxn], h[Maxn], trk[Maxn << 1];

bool cmp(int x, int y, int w) {return trk[x] == trk[y] && trk[x + w] == trk[y + w];}

void SA(int n) {
  static int cnt[Maxn], id[Maxn];
  int m = 300, p = 0;
  for (int i = 1; i <= n; ++i) cnt[rk[i] = s[i]]++;
  for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i; --i) sa[cnt[rk[i]]--] = i;
  for (int w = 1; p != n; w <<= 1, m = p) {
    p = 0;
    for (int i = n; i > n - w; --i) id[++p] = i;
    for (int i = 1; i <= n; ++i) if (sa[i] > w) id[++p] = sa[i] - w;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1; i <= n; ++i) cnt[rk[id[i]]]++;
    for (int i = 1; i <= m; ++i) cnt[i] += cnt[i - 1];
    for (int i = n; i; --i) sa[cnt[rk[id[i]]]--] = id[i];
    memcpy(trk, rk, sizeof(rk));
    p = 0;
    for (int i = 1; i <= n; ++i)
      rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : ++p;
    if (p == n) for (int i = 1; i <= n; ++i) sa[rk[i]] = i;
  }
  for (int i = 1, k = 0; i <= n; ++i) {
    if (k) --k;
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    h[rk[i]] = k;
  }
}

pair <int, int> kth (int n, int k) {
  for (int i = 1, x; i <= n; ++i) {
    x = n - sa[i] + 1 - h[i];
    if (x >= k) return {i, k};
    else k -= x;
  }
  return {0, -1};
}

namespace ST{
  int st[Maxn][33], lg[Maxn];

  void init(int n) {
    for (int i = 1; i <= n; ++i) st[i][0] = h[i];
    for (int k = 1; k <= log2(n); ++k) {
      for (int i = 1; i + (1 << k) - 1 <= n; ++i)
        st[i][k] = min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
    }
  }

  int query(int l, int r, int n) {
    int k = log2(r - l);
    return min(st[l + 1][k], st[r - (1 << k) + 1][k]);
  }
}

signed main() {
  scanf("%s", s + 1);
  int n = strlen(s + 1), t = read(), k = read(), p, w; 
  SA(n);
  if (t == 0){
    auto ans = kth(n, k);
    if (ans.second == -1) return print(-1), 0;
    p = ans.first, w = ans.second;
    for (int i = sa[p]; i <= sa[p] + h[p] + w - 1; ++i)
      putchar(s[i]);
    return 0;
  } else {
    if (k > 1ll * n * (n + 1) / 2) return print(-1), 0;
    int l = 0, r = k;
    ST::init(n);
    while (l < r) {
      int mid = (l + r) >> 1, tot = 0, p, w;
      auto tmp = kth(n, mid);
      p = tmp.first, w = tmp.second;
      for (int i = 1; i < p; ++i)
        tot += n - sa[i] + 1;
      tot += min(w, n - sa[p] + 1);
      for (int i = p + 1; i <= n; ++i)
        tot += min(w, ST::query(p, i, n));
      if (tot >= k) r = mid;
      else l = mid + 1;
    }
    auto ans = kth(n, l); p = ans.first, w = ans.second;
    for (int i = sa[p]; i <= sa[p] + w - 1; ++i)
      putchar(s[i]);
  }
  return 0;
}

题目思路 - $SAM$

对于 $SAM$ 来讲，只要思路对了两种情况差不多。

构建出 $SAM$，对于每个点 $x$ ，统计出以它结尾的子串个数，记为 $siz[x]$ ，利用 $siz$ 统计出经过它的所有子串个数，记为 $sum[x]$ 。

至于如何去求 $siz$ 和 $min$ ，大概有两种方法，一种是常规的倒着连 $fail$ 然后跑 $dfs$ 或 $bfs$ ，而另一种则是对 $len$ 从小到大进行排序，倒着扫更新（当然不能直接对 $len$ 排序，而是要建立一个映射关系。） 这样就能保证更新 $fail[x]$ 时已经更新过 $x$ 了。对于条件 $1$ 在求 $sum$ 之前将每个点的 $siz$ 赋成 $1$ 即可。

递归进行输出，每到一个点 $a\sim z$ 枚举转移边，比较 $k$ 和 $sum[sam[p][i]]$ 的大小关系。

• $k > sum[sam[p][i]]$ 说明要找的点不经过这个转移边，$k = k - sum[sam[p][i]]$。
• $k \le sum[sam[p][i]]$ 说明要找的点需要经过这个转移边。输出 $i$ 并递归。结束后直接回溯防止重复输出。

类似 $01trie$ 二分，只不过多了几个边。

时间复杂度： $O(n)$ 洛谷数据 $4.3s^+$ 表现还可以。$\huge\text{关键是它代码还短}。$ 所以为什么我要写 $SA$ a?

题目代码 - $SAM$

代码

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO // namespace IO
using namespace IO;
const int Maxn = 2e6 + 10;
using namespace std;

int sam[Maxn][26], fail[Maxn], len[Maxn], lst, tot;
int siz[Maxn], sum[Maxn];

void SAM() {len[0] = 0, fail[0] = -1, lst = tot = 0;}

void insert(char c) {
  int p = lst, np = ++tot, ch = c - 'a';
  lst = np, len[np] = len[p] + 1, siz[np] = 1;
  for (; p != -1 && !sam[p][ch]; p = fail[p]) sam[p][ch] = np;
  if (p == -1) return fail[np] = 0, void();
  int q = sam[p][ch];
  if (len[q] == len[p] + 1) return fail[np] = q, void();
  int nq = ++tot;
  fail[nq] = fail[q], fail[np] = fail[q] = nq;
  memcpy(sam[nq], sam[q], sizeof(sam[nq]));
  len[nq] = len[p] + 1, siz[nq] = 0;
  for (; p != -1 && sam[p][ch] == q; p = fail[p]) sam[p][ch] = nq;
}

void print_kth(int p, int k) {
  if (k <= siz[p]) return;
  k -= siz[p];
  for (int i = 0; i < 26; ++i) {
    if (!sam[p][i]) continue;
    if (sum[sam[p][i]] >= k)
      return putchar(i + 'a'), print_kth(sam[p][i], k);
    else k -= sum[sam[p][i]];
  }
}

signed main() {
  static char s[Maxn];
  static int cnt[Maxn], id[Maxn];
  scanf("%s", s); SAM();
  int n = strlen(s), t = read(), k = read();
  for (int i = 0; i < n; ++i) insert(s[i]);
  // 基数排序建立 len 从小到大映射关系
  for (int i = 0; i <= tot; ++i) ++cnt[len[i]];
  for (int i = 0; i <= tot; ++i) cnt[i] += cnt[i - 1];
  for (int i = 0; i <= tot; ++i) id[--cnt[len[i]]] = i;  
  // end
  // 求 siz 和 sum
  for (int i = tot; i >= 0; --i) siz[fail[id[i]]] += siz[id[i]];
  for (int i = 0; i <= tot; ++i) 
    sum[i] = (t == 0 ? (siz[i] = 1) : siz[i]); // 注意这里
  siz[0] = sum[0] = 0;
  for (int i = tot; i >= 0; --i)
    for (int j = 0; j < 26; ++j)
      if (sam[id[i]][j]) sum[id[i]] += sum[sam[id[i]][j]];
  // end
  if (sum[0] < k) return print(-1), 0;
  print_kth(0, k);
  return 0;
}

总结

通过写这道题收获不小，大概掌握了后缀数据结构处理第 $k$ 大子串的方法。

主要为 $SA$ 找第 $k$ 大（本质不同）子串，$SA$ 求一个子串的排名，$SA$ 二分找第 $k$ 大子串。

$SAM$ 求一个串的第 $k$ 小子串。

本文作者：CloudySky
写作时间： 2022-03-08
最后更新时间： 2022-03-08
遵循协议： BY-NC-SA