1. 题目

传送门=￣ω￣=

2. 题解

求出后缀数组和（排名为 $i$的后缀与排名为 $i-1$的后缀的最长公共前缀）即可。

具体参加 KBの【算法】后缀三兄弟之二——后缀数组　　——litble（在文章尾部有讲 QvQ，Thanks KB%%%%

代码：

#include <bits/stdc++.h>
#define NS (100005)
using namespace std;
typedef long long LL;
LL n,rc,x[NS],y[NS],sa[NS],T[130],h[NS],ans;
char s[NS];
void Rsort()
{
    for(LL i=1;i<=rc;i++)T[i]=0;
    for(LL i=1;i<=n;i++)T[x[y[i]]]++;
    for(LL i=1;i<=rc;i++)T[i]+=T[i-1];
    for(LL i=n;i;i--)sa[T[x[y[i]]]--]=y[i];
}
int main()
{
    scanf("%lld%s",&n,s+1);
    for(LL i=1;i<=n;i++)x[i]=s[i],y[i]=i;
    rc=127,Rsort();
    for(LL l=1,tmp=1;tmp<n;l<<=1,rc=tmp)
    {
        tmp=0;
        for(LL i=n-l+1;i<=n;i++)y[++tmp]=i;
        for(LL i=1;i<=n;i++)if(sa[i]>l)y[++tmp]=sa[i]-l;
        Rsort(),swap(x,y),tmp=x[sa[1]]=1;
        for(LL i=2;i<=n;i++)
            if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+l]==y[sa[i-1]+l])x[sa[i]]=tmp;
            else x[sa[i]]=++tmp;
    }
    for(LL i=1,lcp=0,j;i<=n;i++)
    {
        if(lcp)lcp--;
        j=sa[x[i]-1];
        while(s[i+lcp]==s[j+lcp])lcp++;
        h[x[i]]=lcp;
    }
    for(LL i=1;i<=n;i++)ans+=(n-sa[i]+1-h[i]);
    printf("%lld\n",ans);
    return 0;
}