CSU 1656 Paper of FlyBrother：後綴數組求不同子串個數

問題轉化

字符串長度 n ≤ 1e5。不同子串總數 = 所有後綴長度之和 − 相鄰後綴 LCP 之和。
即 ans = n(n+1)/2 - ∑_{i=1}^{n-1} height[i]，其中 height[i] = SA[i] 與 SA[i-1] 的最長公共前綴。

後綴數組構建：倍增算法 O(n log n)

void buildSA(string s) {
    int n = s.size(); s += '$'; // 哨兵
    vector sa(n+1), rnk(n+1), tmp(n+1);
    for (int i=0;i<=n;++i) { sa[i]=i; rnk[i]=s[i]; }
    for (int k=1;k<=n;k<<=1) {
        auto cmp = [&](int i, int j) {
            if (rnk[i]!=rnk[j]) return rnk[i]

void buildHeight(string s, vector& sa, vector& height) {
    int n = s.size();
    vector rnk(n+1);
    for (int i=1;i<=n;++i) rnk[sa[i]] = i;
    int h = 0;
    for (int i=0;i 1) {
            int j = sa[rnk[i]-1];
            while (i+h

long long countDistinctSubstrings(string s) {
    int n = s.size();
    vector sa, height;
    buildSA(s); buildHeight(s, sa, height);
    long long total = 1LL * n * (n + 1) / 2;
    for (int i=2;i<=n;++i) total -= height[i];
    return total;
}