Rockdu's Blog

后缀数组模板题，直接看注释就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int maxn = 1e5 + 5;
char s[maxn]; LL ans;
int SA[maxn], SA2[maxn], RK[maxn], tot[maxn], H[maxn];

//SA : 第一关键字排名为i的开头下标
//SA2 : 第二关键字排名为i的开头下标
//RK : 原字符串中下标为i后缀的排名 

void Rsort(int n, int mx) {
    for(register int i = 1; i <= mx; ++i) tot[i] = 0;
    for(register int i = 1; i <= n; ++i) ++tot[RK[SA2[i]]];
    for(register int i = 1; i <= mx; ++i) tot[i] += tot[i - 1];
    for(register int i = n; i >= 1; --i) SA[tot[RK[SA2[i]]]--] = SA2[i];
}

bool cmp(int x, int y, int l) {
    return SA2[x] == SA2[y] && SA2[x + l] == SA2[y + l];
}

void GetSA(char *s) {
    int n = strlen(s + 1);
    for(register int i = 1; i <= n; ++i)
        RK[i] = s[i], SA2[i] = i;
    Rsort(n, 128);
    for(register int l = 1, p; l < n; l <<= 1) {
        p = 0;
        for(register int i = n - l + 1; i <= n; ++i)
            SA2[++p] = i;
        for(register int i = 1; i <= n; ++i)
            if(SA[i] > l) SA2[++p] = SA[i] - l;
        Rsort(n, p), swap(SA2, RK);
        RK[SA[1]] = p = 1;
        for(register int i = 2; i <= n; ++i)
            RK[SA[i]] = cmp(SA[i], SA[i - 1], l) ? p : (++p);
    }
    
    for(register int i = 1, k = 0, j; i <= n; H[RK[i++]] = k) 
        for(k ? k-- : k, j = SA[RK[i] - 1]; s[i + k] == s[j + k]; ++k);
    ans = n - SA[1] + 1;
    for(register int i = 2; i <= n; ++i)
        ans += n - SA[i] + 1 - H[i];
    printf("%lld\n", ans);
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", s + 1);
        GetSA(s);
    }
    return 0;
}