【SAM】差异（P4248）,索爱w580c软件（索爱w580评测）

文件名：【SAM】差异（P4248）,索爱w580c软件 【SAM】差异（P4248） 正题

P4248

---

题目大意

设$T_i$为第i个字符开始的后缀，求：

$$\sum _{i=1}^n\sum _{j=i+1}^{n}len(T_i)+len(T_j)-2\times lcp(T_i,T_j)$$

---

解题思路

用SAM建立parent树

parent树中一个点x的不同儿子会产生贡献${\sum }_{y\in so{n}_x}(le{n}_y-le{n}_x)\times s{z}_y$（当前子串会重合，而后面部分不重合）

那么可以在x和son之间建立长为$le{n}_y-le{n}_x$的边，然后跑dfs

---

code #include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#define ll long long#define N 500100using namespace std;ll n,w,lst,tot,ans,h[N<<1],sz[N<<1],fa[N<<1],len[N<<1],ch[N<<1][30];char s[N];struct rec{ll to,nx,l;}e[N<<1];void addl(ll x,ll y,ll z){e[++tot].to=y;e[tot].l=z;e[tot].nx=h[x];h[x]=tot;return;}void add(ll c){ll p=lst,np=lst=++w;sz[np]=1;len[np]=len[p]+1;while(p&&!ch[p][c])ch[p][c]=np,p=fa[p];if(!p)fa[np]=1;else{ll q=ch[p][c];if(len[q]==len[p]+1)fa[np]=q;else{ll nq=++w;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[q]));fa[nq]=fa[q];fa[np]=fa[q]=nq;while(p&&ch[p][c]==q)ch[p][c]=nq,p=fa[p];}}return;}void dfs(ll x){for(ll i=h[x];i;i=e[i].nx){ll y=e[i].to;dfs(y);ans+=(n-sz[y])*sz[y]*e[i].l;sz[x]+=sz[y];}return;}int main(){scanf("%s",s+1);n=strlen(s+1);lst=w=1;for(ll i=1;i<=n;++i)add(s[i]-'a');for(ll i=2;i<=w;++i)addl(fa[i],i,len[i]-len[fa[i]]);dfs(1);printf("%lld",ans);return 0;}