后缀自动机好题。

题意：

---

做法：$sam$ 废话

考虑翻转字串，这样后缀的最长公共前缀等于前缀的最长公共后缀。

然后想到$parent$树上面两个串的最长公共后缀跟他们所处状态的$lca$有关系。

于是对于每一个$lca$都处理出它的$size$和maxlengthmax_{length}maxlength​就行了。

代码：

#include
    
     #define ri register intusing namespace std;typedef long long ll;const int N=1e6+5;int n;char s[N];struct SAM{
    	int last,rt,tot,link[N],len[N],siz[N],son[N][26],rk[N],cnt[N];	SAM(){
    rt=last=tot=1,len[0]=-1,fill(son[0],son[0]+26,1);}	inline void expand(int x){
    		int p=last,np=++tot;		siz[last=np]=1,len[np]=len[p]+1;		while(p&&!son[p][x])son[p][x]=np,p=link[p];		if(!p){
    link[np]=rt;return;}		int q=son[p][x],nq;		if(len[q]==len[p]+1){
    link[np]=q;return;}		len[nq=++tot]=len[p]+1,memcpy(son[nq],son[q],sizeof(son[q])),link[nq]=link[q];		while(p&&son[p][x]==q)son[p][x]=nq,p=link[p];		link[np]=link[q]=nq;	}	inline void topsort(){
    		ll ans=(ll)(n-1)*n*(n+1)/2;		for(ri i=1;i<=tot;++i)++cnt[len[i]];		for(ri i=1;i<=last;++i)cnt[i]+=cnt[i-1];		for(ri i=1;i<=tot;++i)rk[cnt[len[i]]--]=i;		for(ri i=tot;i;--i)siz[link[rk[i]]]+=siz[rk[i]];		for(ri i=2;i<=tot;++i)ans-=(ll)(len[i]-len[link[i]])*siz[i]*(siz[i]-1);		cout<