正题
题目链接:https://ac.nowcoder.com/acm/contest/20110/D
题目大意
求一个长度为(n)的字符串的所有子串的(border)长度和。
(1leq nleq 10^5)
解题思路
考虑到两个相同的子串会作为一个子串的(border)，所以问题可以变为求所有相同子串对的长度之和。
然后直接跑出(SAM)然后对于每个节点统计它在字符串里的出现次数，然后所有的(len_{fa+1}sim len_x)都是这个节点的字符串长度，用过等比序列求和就好了。
时间复杂度：(O(n))（不算快速排序）
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e5+10;
ll n,cnt,last,ans,p[N],len[N],fa[N],c[N],ch[N][26];
char s[N];
void Insert(char c){
ll p=last,np=last=++cnt;
len[np]=len[p]+1;
for(;!ch[p][c];p=fa[p])ch[p][c]=np;
if(!p)fa[np]=1;
else{
ll q=ch[p][c];
if(len[p]+1==len[q])fa[np]=q;
else{
ll nq=++cnt;len[nq]=len[p]+1;
memcpy(ch[nq],ch[q],sizeof(ch[nq]));
fa[nq]=fa[q];fa[q]=fa[np]=nq;
for(;ch[p][c]==q;p=fa[p])ch[p][c]=nq;
}
}
return;
}
bool cmp(ll x,ll y)
{return len[x]>len[y];}
ll calc(ll l,ll r){
if(!r)return 0;
return (r+l)*(r-l+1)/2;
}
signed main()
{
scanf("%lld",&n);
scanf("%s",s+1);cnt=last=1;
for(ll i=1;i<=n;i++)Insert(s[i]-'a'),c[last]++;
for(ll i=1;i<=cnt;i++)p[i]=i;
sort(p+1,p+1+cnt,cmp);
for(ll i=1;i<=cnt;i++)c[fa[p[i]]]+=c[p[i]];
for(ll i=1;i<=cnt;i++){
ll w=calc(len[fa[i]]+1,len[i]);
ans+=calc(1,c[i]-1)*w;
}
printf("%lld
",ans);
return 0;
}