[BZOJ3238][Ahoi2013]差异（后缀自动机）

还是字符串题。

Source

https://www.lydsy.com/JudgeOnline/problem.php?id=3238

Solution

出于练手的目的，用 SAM 把此题再写了一遍，再次了解了 SAM 的妙用。
后缀数组做法：https://blog.csdn.net/xyz32768/article/details/78991972
首先要了解：后缀自动机 SAM 如何求原串两个前缀的最长公共后缀。
先找到这两个前缀在 SAM 中对应的状态 u,v$u,v$ 。
此外，我们知道，在 Parent 树中不断地往上跳就是不断地寻找后缀的过程。
因此，这两个前缀的最长公共后缀就是 Parent 树上 u$u$ 和 v$v$ 的 LCA 状态能表示出的最长子串。
于是可以将原串倒过来，那么后缀的最长公共前缀就变成了前缀的最长公共后缀。问题转化为：构建好 SAM 和 Parent 树，以及一些关键点（能表示出原串的前缀的状态），求每对点 (u,v)$(u,v)$ 的

MaxlLCA(u,v)$$Max{l}_{\text{LCA}(u,v)}$$

之和。
Maxli$Max{l}_i$ 为状态 i$i$ 能表示的最长子串长度。
由于在 Parent 树上往上跳是 Right$Right$ 集不断合并的过程，因此对于一个状态 u$u$ ，它的 Right$Right$ 集大小等于 u$u$ 的子树内关键点的个数。
所以，对于一个点 u$u$ ，它是

|Rightu|×(|Rightu|−1)2−∑v∈son(u)|Rightv|×(|Rightv|−1)2$$\frac{|Righ{t}_u|\times (|Righ{t}_u|-1)}{2}-\sum _{v\in son(u)}\frac{|Righ{t}_v|\times (|Righ{t}_v|-1)}{2}$$

对点的 LCA 。
上式的理解： u$u$ 的子树里的 |Rightu|×(|Rightu|−1)2$\frac{|Righ{t}_u|\times (|Righ{t}_u|-1)}{2}$ 对点都有公共祖先 u$u$ ，但如果一对点同时在 v$v$ 的子树内（ v$v$ 是 u$u$ 在 Parent 树上的子状态），那么这样的点对的 LCA 就不是 u$u$ ，必须去除。
于是一个状态 u$u$ 对 ∑1≤i<j≤nlcs(Suffixi,Suffixj)$\sum _{1\le i<j\le n}\text{lcs}(Suffi{x}_i,Suffi{x}_j)$ 的贡献为：

(|Rightu|×(|Rightu|−1)2−∑v∈son(u)|Rightv|×(|Rightv|−1)2)×Maxlu$$(\frac{|Righ{t}_u|\times (|Righ{t}_u|-1)}{2}-\sum _{v\in son(u)}\frac{|Righ{t}_v|\times (|Righ{t}_v|-1)}{2})\times Max{l}_u$$

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define SAM(hnoi) for (; i && hnoi; i = T[i].fa)
#define ParentTree(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
typedef long long ll;
const int N = 1e6 + 5;
struct cyx {
    int fa, go[26], ri, maxl;
    void init() {fa = ri = maxl = 0; memset(go, 0, sizeof(go));}
} T[N];
int n, QAQ, lst, ecnt, nxt[N], adj[N], go[N]; char s[N]; ll ans;
void add_edge(int u, int v) {
    nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
}
void extend(int c) {
    int i = lst; T[lst = ++QAQ].init(); T[lst].maxl = T[i].maxl + 1;
    T[lst].ri = 1; SAM(!T[i].go[c]) T[i].go[c] = lst;
    if (!i) T[lst].fa = 1; else {
        int j = T[i].go[c]; if (T[i].maxl + 1 == T[j].maxl) T[lst].fa = j;
        else {
            int p; T[p = ++QAQ] = T[j]; T[p].ri = 0;
            T[lst].fa = T[j].fa = p; T[p].maxl = T[i].maxl + 1;
            SAM(T[i].go[c] == j) T[i].go[c] = p;
        }
    }
}
void dfs(int u) {
    ParentTree(u) dfs(v), T[u].ri += T[v].ri;
    ll cnt = 1ll * T[u].ri * (T[u].ri - 1); ParentTree(u)
        cnt -= 1ll * T[v].ri * (T[v].ri - 1); cnt >>= 1;
    ans += cnt * T[u].maxl;
}
void SuffixAutomaton() {
    int i; For (i, 2, QAQ) add_edge(T[i].fa, i); dfs(1);
}
int main() {
    int i; scanf("%s", s + 1); n = strlen(s + 1); T[QAQ = lst = 1].init();
    Rof (i, n, 1) extend(s[i] - 'a'); SuffixAutomaton();
    cout << (1ll * (n - 1) * n * (n + 1) >> 1) - (ans << 1) << endl; return 0;
}