SPOJ - 694 New Distinct Substrings

传送门：SPOJ - 694

思路分析

子串一定是某一个后缀的前缀，后缀排序之后，每加入一个排名$i$的后缀，产生了$n-sa[i]+1$个前缀，那么重复的部分就是$h[i]$

AC代码

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define fun function
#define sz(x) (int)(x).size()
#define lowbit(x) (x)&(-x)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int N = 1e6+10;

struct Suf_Array {
    int h[N], rk[N], sa[N], y[N], c[N];
    void build(char *str,int n, int m) {
        for (int i = 0; i <= m; i ++) c[i] = 0;
        for (int i = 1; i <= n; i ++) c[rk[i] = (str[i])] ++;
        for (int i = 1; i <= m; i ++) c[i] += c[i - 1];
        for (int i = n; i >= 1; i --) sa[c[rk[i]]--] = i;
        for (int k = 1; k <= n; k <<= 1) {
            int p = 0;
            for (int i = n - k + 1; i <= n; i ++) y[++p] = i;
            for (int i = 1; i <= n; i ++) if (sa[i] > k) y[++p] = sa[i] - k;
            for (int i = 0; i <= m; i ++) c[i] = 0;
            for (int i = 1; i <= n; i ++) c[rk[i]]++;
            for (int i = 1; i <= m; i ++) c[i] += c[i - 1];
            for (int i = n; i >= 1; i --) sa[c[rk[y[i]]]--] = y[i];
            swap(rk, y);
            rk[sa[1]] = p = 1;
            for (int i = 2; i <= n; i ++)
                rk[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);
            if (p >= n) break;
            m = p;
        }
        for (int i = 1, k = 0; i <= n; i ++) {
            if (k) -- k;
            int j = sa[rk[i] - 1];
            while (str[i + k] == str[j + k]) k ++;
            h[rk[i]] = k;
        }
    }
} SA;

char s[N];

signed main() {

#ifdef xiaofan
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif

    int T;
    cin>>T;
    while(T--) {
        cin>>s+1;
        int n = strlen(s+1);
        SA.build(s,n,128);
        ll ans = 0;
        for(int i=1;i<=n;i++) ans+= n - SA.sa[i]+1-SA.h[i];
        cout<<ans<<endl;
    }





    return 0;
}