SAM-DAG 链剖分小记

算法简述

这个东西出现在 UOJ697【候选队互测2022】广为人知题，也许是比较新的科技。

在 SAM 的 DAG 上，对每个结点 \(x\)，记以 \(x\) 为终点的有 \(f_x\) 条，以 \(x\) 为起点的路径有 \(g_x\) 条。则令 \((x,y)\) 为重边当且仅当 \(2f_x>f_y, 2g_y>g_x\)。

对于一条轻边，\(2g_y \leq g_x\) 或 \(2f_x \leq f_y\)，意味着 \(g\) 除以 2 或者 \(f\) 乘 2。在一般 DAG 上 \(g, f\) 关于 \(n\) 是指数级别的，但是 在 SAM 上 是 \(O(poly(n))\) 级别的，所以一条路径上至多有 \(O(\log n)\) 条轻边，可以将一条路径拆分成 \(O(\log n)\) 条重链。

代码

预处理

dfs序从0开始，同一条重链上的pos是连续的，ht是到重链底端的距离，从零开始。

int in[N], id[N], dfn, pos[N], ht[N];

void dag_hld() {
  std::vector<LL> f(cnt + 1, 1), g(cnt + 1, 1);
  std::vector<int> p(cnt + 1);

  std::iota(p.begin(), p.end(), 0);
  std::sort(p.begin(), p.end(), [&](int i, int j) { return len[i] < len[j]; });

  for (int i : p) {
    for (int j = 0; j < 26; j++) {
      if (ch[i][j]) f[ch[i][j]] += f[i];
    }
  }
  for (int i = cnt; i >= 0; i--) {
    int x = p[i];
    for (int j = 0; j < 26; j++) {
      if (ch[x][j]) g[x] += g[ch[x][j]];
    }
  }

  std::function<void(int)> dfs = [&](int x) {
    in[x] = dfn++;
    id[in[x]] = x;
    for (int i = 0; i < 26; i++) {
      int y = ch[x][i];
      if (y && 2 * f[x] > f[y] && 2 * g[y] > g[x]) {
        dfs(y);
        pos[x] = pos[y] - 1;
        ht[x] = ht[y] + 1;
      }
    }
  };

  for (int i : p)
    if (!i || !in[i]) dfs(i);
}

定位

定位 \(S[l, r)\)。

int o = 0, match = 0;
while (l < r) {
  o = ch[o][s[l] - 'a'];
  if (!o) break;
  int k = std::min({ht[o] + 1, r - l, sa.lcp(l, pos[o])});
  // interval [in[o], in[o] + k)
  l += k;
  match += k;
  o = id[in[o] + k - 1];
}

最后修改于 2022-08-14