正題

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 500100 using 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; }

總結

以上是生活随笔為你收集整理的【SAM】差异（P4248）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。