P4248 [AHOI2013] 差异 题解

Description

给定一个长度为 $n$ 的字符串 $S$，令 $T_i$ 表示它从第 $i$ 个字符开始的后缀。求 $\displaystyle \sum_{1\leq ij\leq n}\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$。

其中，$\text{len}(a)$ 表示字符串 $a$ 的长度，$\text{lcp}(a,b)$ 表示字符串 $a$ 和字符串 $b$ 的最长公共前缀。

link

Solution

考虑把 $S$ 的反串的 parent 树建出来。

设 $T_i$ 的 endpos 等价类是 $x$，$T_j$ 的 endpos 等价类是 $y$。

由于 parent 树上任意一个点的父亲一定是这个点的后缀，所以 $T_i$ 和 $T_j$ 的公共前缀一定就在反串 parent 树上 $x$ 和 $y$ 某个公共祖先所表示的等价类里，而最长的一定就在 $x$ 和 $y$ 的 LCA 上。

由于 $T_i,T_j$ 和 $\text{lcp}(T_i,T_j)$ 一定都是反串的前缀，所以他们的长度一定都是所在等价类最大的，那么 $\text{len}(T_i)+\text{len}(T_j)-2\times\text{lcp}(T_i,T_j)$ 就等于 $\text{len}_x+\text{len}_y-2\times \text{len}_\text{lca}$，如果把 parent 树的边权看作相邻两点 $\text{len}$ 的差值，那么原式就是 $x,y$ 的树上最短路径的长度。

然后对于每条边算贡献即可，即设 $\text{size}_x$ 表示 $x$ 的子树里反串前缀所在的等价类的个数，答案就是 $\displaystyle\sum\left(\text{size}_x\times(n-\text{size}_x)\times(\text{len}_x-\text{len}_\text{fa})\right)$。

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

Code

#include <cstdio>
#include <iostream>
#include <vector>

// #define int int64_t

const int kMaxN = 1e6 + 5;

using i64 = int64_t;

int n, tot = 1, lst = 1, nxt[kMaxN][26], len[kMaxN], fa[kMaxN], sz[kMaxN];
i64 ans;
std::vector<int> G[kMaxN];

void ins(int c) {
  int cur = ++tot, p = lst;
  lst = cur;
  len[cur] = len[p] + 1, sz[cur] = 1;
  for (; p && !nxt[p][c]; p = fa[p]) nxt[p][c] = cur;
  if (!p) {
    fa[cur] = 1;
  } else {
    int q = nxt[p][c];
    if (len[q] == len[p] + 1) {
      fa[cur] = q;
    } else {
      int nw = ++tot;
      fa[nw] = fa[q], len[nw] = len[p] + 1;
      for (int i = 0; i < 26; ++i)
        nxt[nw][i] = nxt[q][i];
      fa[q] = fa[cur] = nw;
      for (; p && nxt[p][c] == q; p = fa[p]) nxt[p][c] = nw;
    }
  }
}

void dfs(int u) {
  for (auto v : G[u]) {
    dfs(v);
    sz[u] += sz[v];
    ans += (i64)sz[v] * (n - sz[v]) * (len[v] - len[u]);
  }
}

void dickdreamer() {
  std::string s;
  std::cin >> s;
  n = s.size();
  for (int i = n - 1; ~i; --i)
    ins(s[i] - 'a');
  for (int i = 2; i <= tot; ++i)
    G[fa[i]].emplace_back(i);
  dfs(1);
  std::cout << ans << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}