\(\frac{n\times n+1}{2}\) 个子串，减去重复的（height 的 和）

“产生前缀” 的意思是 sa[i] 这个后缀有 n-sa[i]+1 个前缀

#include 
    
     using namespace std;int k, n, rnk[50005], sa[50005], H[50005], c[50005], K;char s[50005];void Sort(int *x, int *y, int *rk) {  static int C[50005];  for (int i = 0; i <= k; ++i) C[i] = 0;  for (int i = 1; i <= n; ++i) ++C[rk[i]];  for (int i = 1; i <= k; ++i) C[i] += C[i - 1];  for (int i = n; i; --i) y[C[rk[x[i]]]--] = x[i];}inline bool cmp(int *y, int a, int b, int m) {return y[a] == y[b] && y[a + m] == y[b + m];}void get_SA() {  static int Y[50005];  int *y = Y, *rk = rnk;  for (int i = 1; i <= n; ++i) rk[i] = s[y[i] = i];  k = 128;  Sort(y, sa, rk);  for (int m = 1, p = 0; p < n; k = p, m <<= 1) {    for (p = 0; p < m; ++p) y[p + 1] = n - m + p + 1;    for (int i = 1; i <= n; ++i) if (sa[i] > m) y[++p] = sa[i] - m;    Sort(y, sa, rk), swap(y, rk);    rk[sa[p = 1]] = 1;    for (int i = 2; i <= n; ++i) rk[sa[i]] = cmp(y, sa[i], sa[i - 1], m) ? p : ++p;  }  for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;}void get_H() {  for (int i = 1, k = 0; i <= n; H[rnk[i++]] = k)    for (k ? --k : 0; s[i + k] == s[sa[rnk[i] - 1] + k]; ++k);}int main() {  cin >> K;  while (~scanf("%s", s + 1)) {    n = strlen(s + 1);    get_SA();    get_H();    unsigned int ans = n * 1ll * (n + 1) / 2;    for (int i = 2; i <= n; ++i) ans -= H[i];    cout << ans << endl;  }  return 0;}