SP705

· · 题解

后缀数组模板应用，与 SP694 相同。

题目大意

给定一个长度为 n \le 50000 的字符串，求字符串中本质不同的子串个数。

大体思路

考虑用后缀数组。由于每一个子串一定是一个后缀的前缀，因此本质不同的子串个数问题可以转化为所有后缀之间不同前缀的个数。

考虑排名为 i 的后缀，其长度为 n-sa_i+1。由定义可知，height_i 表示排名为 i 与 i-1 的后缀的最长公共前缀，即重复的前缀个数，所以该后缀的贡献为 (n-sa_i+1)-height_i。因为所有后缀按照字典序排序，不存在某一前缀 S' 不为排名为 i, i-1 的公共前缀，却为 i, i-k(k>1) 的公共前缀，所以上述贡献不重不漏。

当然，也可以利用容斥原理，所有的子串个数为 \dfrac{n(n+1)}2，减去重复子串个数 \sum height_i 即可。

总而言之，答案为

\sum_{i=1}^n (n-sa_i+1)-height_i=\dfrac{n(n+1)}2-\sum_{i=1}^n height_i

完整代码

#include <bits/stdc++.h>
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int, int> PII;
const int maxn = 50000 + 5;
namespace IO_ReadWrite {
    #define re register
    #define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
    char _buf[1<<21], *p1 = _buf, *p2 = _buf;
    template <typename T>
    inline void read(T &x){
        x = 0; re T f=1; re char c = gg;
        while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
        while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
        x *= f;return;
    }
    inline void ReadChar(char &c){
        c = gg;
        while(!isalpha(c)) c = gg;
    }
    template <typename T>
    inline void write(T x){
        if(x < 0) putchar('-'), x = -x;
        if(x > 9) write(x/10);
        putchar('0' + x % 10);
    }
    template <typename T>
    inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
int T, n, m;
char s[maxn];
int x[maxn], y[maxn], cnt[maxn], sa[maxn], rk[maxn], height[maxn];
inline void getSA() {
    rep(i, 1, n) cnt[x[i] = s[i]] ++;
    rep(i, 2, m) cnt[i] += cnt[i - 1];
    Rep(i, n, 1) sa[cnt[x[i]] --] = i;
    for(int k = 1; k <= n; k <<= 1) {
        int tot = 0;
        rep(i, n - k + 1, n) y[++tot] = i;
        rep(i, 1, n)
            if(sa[i] > k) y[++tot] = sa[i] - k;
        rep(i, 1, m) cnt[i] = 0;
        rep(i, 1, n) cnt[x[i]] ++;
        rep(i, 2, m) cnt[i] += cnt[i - 1];
        Rep(i, n, 1) sa[cnt[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, tot = 1;
        rep(i, 2, n)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? tot : ++tot;
        if(tot == n) break;
        m = tot;
    }
}
inline void getH() {
    rep(i, 1, n) rk[sa[i]] = i;
    for(int i = 1, k = 0; i <= n; i ++) {
        if(rk[i] == 1) continue;
        if(k) k --;
        int j = sa[rk[i] - 1];
        while(j + k <= n && i + k <= n && s[i + k] == s[j + k]) k ++;
        height[rk[i]] = k;
    }
}
inline void solve() {
    memset(sa, 0, sizeof sa);
    memset(cnt, 0, sizeof cnt);
    memset(height, 0, sizeof height);
    memset(rk, 0, sizeof rk); // 多测清空
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 128;
    getSA(); getH();
    ll ans = 0;
    rep(i, 1, n) 
        ans += (ll)(n - sa[i] + 1 - height[i]);
    writeln(ans);
}
int main () {
    scanf("%d", &T);
    while(T --) solve();    
    return 0;
}