本文共 962 字，大约阅读时间需要 3 分钟。

万能的后缀树啊2333

建出后缀树，一个节点的祖先节点都是他的后缀，一个节点的儿子节点都是以他为后缀的串。所以两个串的lcs就是他们的lca节点的 $len$ 。

这道题可以对反串建后缀树，树边 $(u,v)$ 权值为 $|le{n}_u-le{m}_v|$ ，答案就是所有关键点之间的路径权值之和。

#include
   
    #define N 1000006using namespace std;typedef long long ll;char s[N];int lst,cnt,link[N];ll n,ans,len[N],siz[N];vector
    
      son[N];struct SAM{   	map
     
       trans[N];	void insert(char c){   		int z=++cnt,p=lst; siz[z]=1,len[z]=len[lst]+1;		while(p!=-1&&!trans[p].count(c))trans[p][c]=z,p=link[p];		if(p==-1) link[z]=0;		else{   			int q=trans[p][c];			if(len[q]==len[p]+1) link[z]=q; 			else{   				int clone=++cnt; len[clone]=len[p]+1;				trans[clone]=trans[q];				while(p!=-1&&trans[p][c]==q) trans[p][c]=clone,p=link[p];				link[clone]=link[q],link[z]=link[q]=clone;			}		}		lst=z;	}	void dp(int x=0){   		int y;		for(int i=0;i
      
       =1;i--) sam.insert(s[i]);	for(int i=1;i<=cnt;i++) son[link[i]].push_back(i);	sam.dp();	cout<