題目鏈接

\(Description\)

給定n個串和K，求每個串中有多少個子串是這n個串中至少K個串的子串。

\(Solution\)

同上題，我們可以算出每個節點所代表的串出現在了幾個串中；而且我們知道，對于每個節點i，它代表的串的數量為len[i]-len[fa[i]]。
建立廣義后綴自動機，預處理每個節點的cnt。每個節點的val可以根據cnt是否>=K設為len[i]-len[fa[i]]或0。
我們要求的是所有子串，所以如果統計val[i]，也要算上val[fa[i]],val[fa[fa[i]]]...直接建出parent樹從上到下DFS更新每個點。
對于每個要求答案的串，在SAM上走一遍并累加所有經過節點的更新后的val即可。
求答案的時候因為不方便存所有原串，so用個鏈表/vector存下所有經過點來。

如果有拓撲序的話也不需要建parent樹DFS。

我并不想看100+行的SA+二分。。

跑得略慢啊

//30740kb 612ms #include <cstdio> #include <vector> #include <cstring> #include <algorithm> #define gc() getchar() typedef long long LL; const int N=2e5+5;//∑len <= 1e5 ?struct Suffix_Automaton {int n,K,las,tot,fa[N],son[N][26],len[N],cnt[N],bef[N],Enum,H[N],nxt[N],to[N];//parent樹空間是2n啊 LL val[N];char s[N>>1];std::vector<int> v[N>>1];void Init(int nn){n=nn, scanf("%d",&K), las=tot=1;}inline void AddEdge(int u,int v){to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;}void Insert(int now,int c){int p=las,np=++tot; len[las=np]=len[p]+1;for(; p&&!son[p][c]; p=fa[p]) son[p][c]=np;if(!p) fa[np]=1;else{int q=son[p][c];if(len[q]==len[p]+1) fa[np]=q;else{int nq=++tot;len[nq]=len[p]+1, bef[nq]=bef[q], cnt[nq]=cnt[q];memcpy(son[nq],son[q],sizeof son[q]);fa[nq]=fa[q], fa[q]=fa[np]=nq;for(; son[p][c]==q; p=fa[p]) son[p][c]=nq;}}v[now].push_back(np);for(; bef[np]!=now&&np; np=fa[np])++cnt[np], bef[np]=now;}void Build(int now){scanf("%s",s), las=1;//las=1！ for(int i=0,l=strlen(s); i<l; ++i)Insert(now,s[i]-'a');}void DFS(int x){val[x]+=val[fa[x]];for(int i=H[x]; i; i=nxt[i]) DFS(to[i]);}void Solve(){for(int i=2; i<=tot; ++i){AddEdge(fa[i],i);if(cnt[i]<K) val[i]=0;else val[i]=len[i]-len[fa[i]];}DFS(1);for(int i=1; i<=n; ++i){LL res=0;for(int j=0,l=v[i].size(); j<l; ++j)res+=val[v[i][j]];printf("%lld ",res);}} }sam;int main() {int n; scanf("%d",&n), sam.Init(n);for(int i=1; i<=n; ++i) sam.Build(i);sam.Solve();return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/9241115.html

總結

以上是生活随笔為你收集整理的BZOJ.3277.串(广义后缀自动机)的全部內容，希望文章能夠幫你解決所遇到的問題。

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