前言
不得不说，这个题真的难，但是在我的不懈坚持之下还是被我给调出来了。
这就是专属于我们的快乐吧，在你做出题的那一刻，欣喜若狂。
解法
统计本质不同的字串数，第一眼看上去是懵的，不知道该从哪里下手，甚至想用广义SAM。
但是其实不用那么麻烦。
我们将子串分为四类，S,S,S,ST,最后算上空集和。
你发现这里面最难搞的就是S*T，前面的直接用最普通的求法求就好了。
就是用当前及节点的len减去parent树上的爹的len，后缀自动机基操吧。
但是楼下好像并没有这样做，我也不知道为什么是对的？？？？？
那么我们就直接去统计S*T。
你会发现这里，结束节点集合相同的S所对应的T是完全相同的。
但是我们无法直接找到这样的集合，不过，parent树上全都是这样的。
这就启发我们在parent树上进行合并，具体是求链并的长度。
这个可以自行百度，所谓链并，就是求一堆点的到lca的长度的集合。
链并的长度就是对于当前S的T的种类数，直接乘上就行了
LCA我是树剖实现的，链并可以用线段树维护。
AC_code
#include<bits/stdc++.h>
using namespace std;
#define re register int
#define int long long
#define ll long long
const int N=2e5+5;
char ch[N];
ll ans;
int to[N],nxt[N],head[N],rp;
void add_edg(int x,int y){
to[++rp]=y;nxt[rp]=head[x];head[x]=rp;
}
int fa[N],dep[N],siz[N],son[N],top[N];
int dfn[N],cnt,idf[N];
int lon[N];
int LCA(int x,int y){
x=idf[x];y=idf[y];
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
x=fa[top[x]];
}
return dep[x]<dep[y]?x:y;
}
struct XDS{
int sum[N*40],ls[N*40],rs[N*40];
int seg,al[N*40],ar[N*40];
void pushup(int x){
if(ls[x])al[x]=al[ls[x]];
else if(rs[x])al[x]=al[rs[x]];
if(rs[x])ar[x]=ar[rs[x]];
else if(ls[x])ar[x]=ar[ls[x]];
if(ls[x]&&rs[x])
sum[x]=sum[ls[x]]+sum[rs[x]]-lon[LCA(ar[ls[x]],al[rs[x]])];
else if(ls[x])sum[x]=sum[ls[x]];
else if(rs[x])sum[x]=sum[rs[x]];
return ;
}
void ins(int &x,int l,int r,int pos){
if(!x)x=++seg;
if(l==r){
al[x]=ar[x]=pos;
sum[x]=lon[idf[pos]];
//cout<<sum[x]<<" "<<idf[pos]<<" "<<pos<<endl;
return ;
}
int mid=l+r>>1;
if(pos<=mid)ins(ls[x],l,mid,pos);
else ins(rs[x],mid+1,r,pos);
pushup(x);return ;
}
int merge(int x,int y){
if(!x||!y)return x+y;
ls[x]=merge(ls[x],ls[y]);
rs[x]=merge(rs[x],rs[y]);
pushup(x);
return x;
}
}xds;
int rt[N];
struct SAM{
struct node{
int fail,son[27];
int len;
node(){};
}tr[N];
int pos[N],seg,las;
SAM(){seg=las=1;}
void dfs_fi(int x){
siz[x]=1;son[x]=0;
lon[x]=tr[x].len;
for(re i=head[x];i;i=nxt[i]){
int y=to[i];fa[y]=x;dep[y]=dep[x]+1;
dfs_fi(y);siz[x]+=siz[y];
if(!son[x]||siz[y]>siz[son[x]])son[x]=y;
}
}
void dfs_se(int x,int f){
top[x]=f;dfn[x]=++cnt;idf[cnt]=x;
if(son[x])dfs_se(son[x],f);
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
if(y==son[x])continue;
dfs_se(y,y);
}
}
void ins(int c,int id){
int p=las,np=++seg;las=np;
tr[np].len=tr[p].len+1;pos[id]=seg;
while(p&&!tr[p].son[c])tr[p].son[c]=np,p=tr[p].fail;
if(!p)tr[np].fail=1;
else {
int q=tr[p].son[c];
if(tr[q].len==tr[p].len+1)tr[np].fail=q;
else {
int nq=++seg;tr[nq]=tr[q];
tr[nq].len=tr[p].len+1;
tr[q].fail=tr[np].fail=nq;
while(p&&tr[p].son[c]==q)tr[p].son[c]=nq,p=tr[p].fail;
}
}
}
void get_slpf(){
for(re i=2;i<=seg;i++)
add_edg(tr[i].fail,i);//cout<<tr[i].fail<<" "<<i<<endl;
dfs_fi(1);dfs_se(1,1);
}
void sol(int x){
for(re i=head[x];i;i=nxt[i]){
int y=to[i];
sol(y);
rt[x]=xds.merge(rt[x],rt[y]);
}
if(x!=1){
ans+=1ll*(tr[x].len-tr[tr[x].fail].len)*xds.sum[rt[x]];
}
//cout<<x<<" "<<ans<<endl;
}
void get_edg(){
memset(head,0,sizeof(head));rp=0;
for(re i=2;i<=seg;i++)add_edg(tr[i].fail,i);
}
}be,af;
signed main(){
scanf("%s",ch+1);
int len=strlen(ch+1);
for(re i=1;i<=len;i++)be.ins(ch[i]-‘a‘,i);
for(re i=len;i>=1;i--)af.ins(ch[i]-‘a‘,i);
for(re i=2;i<=be.seg;i++){
if(be.tr[i].len!=len)ans+=be.tr[i].len-be.tr[be.tr[i].fail].len;
ans+=be.tr[i].len-be.tr[be.tr[i].fail].len;
//S和*S
for(re i=2;i<=af.seg;i++)//T和*T
if(af.tr[i].len!=len)ans+=af.tr[i].len-af.tr[af.tr[i].fail].len;
af.get_slpf();
for(re i=1;i<=len-2;i++)
xds.ins(rt[be.pos[i]],1,cnt,dfn[af.pos[i+2]]);
be.get_edg();
be.sol(1);
printf("%lld",ans+2);
}