算法1

后缀数组，先把式子化简，然后前半部分直接算，后半部分就是一个求所有子区间最小值的和的问题，用单调栈即可

C++ 代码

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long LL;

const int N = 500010;
char s[N];
int x[N], y[N], c[N], rk[N], sa[N], height[N];
int l[N], r[N];
int stk[N], top;
int n, m;

void get_sa()
{
    for(int i = 1; i <= n; ++ i) c[x[i] = s[i]] ++;
    for(int i = 2; i <= m; ++ i) c[i] += c[i - 1];
    for(int i = n; i; -- i) sa[c[x[i]] --] = i;
    for(int k = 1; k <= n; k <<= 1)
    {
        int num = 0;
        for(int i = n - k + 1; i <= n; ++ i) y[++ num] = i;
        for(int i = 1; i <= n; ++ i)
            if(sa[i] > k)
                y[++ num] = sa[i] - k;
        for(int i = 1; i <= m; ++ i) c[i] = 0;
        for(int i = 1; i <= n; ++ i) c[x[i]] ++;
        for(int i = 2; i <= m; ++ i) c[i] += c[i - 1];
        for(int i = n; i; -- i) sa[c[x[y[i]]] --] = y[i], y[i] = 0;
        swap(x, y);
        x[sa[1]] = 1, num = 1;
        for(int i = 2; i <= n; ++ i)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++ num;
        if(num == n) break;
        m = num;
    }
}

void get_height()
{
    for(int i = 1; i <= n; ++ i) 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(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++ k;
        height[rk[i]] = k;
    }
}

LL get_sum()
{
    LL res = 0ll;
    for(int i = 2; i <= n; ++ i) 
    {
        while(top && height[stk[top]] > height[i]) top --;
        if(top) l[i] = stk[top];
        else l[i] = 1;
        stk[ ++ top ] = i;
    }
    top = 0;
    for(int i = n; i >= 2; -- i)
    {
        while(top && height[stk[top]] >= height[i]) top --;
        if(top) r[i] = stk[top];
        else r[i] = n + 1;
        stk[ ++ top ] = i;
    }
    for(int i = 2; i <= n; ++ i) res += (LL)height[i] * (i - l[i]) * (r[i] - i);
    return res;
}

int main()
{
    scanf("%s", s + 1);
    n = strlen(s + 1);
    m = 300;
    get_sa();
    get_height();
    printf("%lld", (LL)(n - 1) * n * (n + 1) / 2 - 2 * get_sum());

    return 0;
}