正題

題目鏈接:https://www.luogu.com.cn/problem/P6139

---

題目大意

求$n$個(gè)串的不同子串個(gè)數(shù)

---

解題思路

如何在$SAM$中插入多個(gè)字符串。
可以我們可以通過更改$last$為之前的節(jié)點(diǎn)來做，如果插入一個(gè)之前插入過的節(jié)點(diǎn)就按照之前$SAM$的方法特判就好了。

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=2e6+10; ll n,m,cnt,last,len[N],fa[N],ch[N][26],ans; char s[N]; ll Ins(ll c,ll last){ll p=last;if(ch[p][c]){ll q=ch[p][c];if(len[p]+1==len[q])return q;else{ll nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;return nq;}}ll np=++cnt;len[np]=len[p]+1;for(;p&&!ch[p][c];p=fa[p])ch[p][c]=np;if(!p)fa[np]=1;else{ll q=ch[p][c];if(len[p]+1==len[q])fa[np]=q;else{ll nq=++cnt;len[nq]=len[p]+1;memcpy(ch[nq],ch[q],sizeof(ch[nq]));fa[nq]=fa[q];fa[q]=fa[np]=nq;for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nq;}}return np; } int main() {scanf("%lld",&m);cnt=1;for(ll i=1;i<=m;i++){last=1;scanf("%s",s);n=strlen(s);for(ll j=0;j<n;j++)last=Ins(s[j]-'a',last);}for(ll i=1;i<=cnt;i++)ans+=len[i]-len[fa[i]];printf("%lld",ans); } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的P6139-[模板]广义后缀自动机(广义 SAM)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。