BZOJ5137&&lg4081(廣義后綴自動機，set啟發式合并)

題面

自己找去

HINT

給定多個文本串，讓你查詢每個文本串中有多少個本質不同的子串且這個子串只出現在當前這個文本串中。
把題目拆成兩個部分，你要先確定這個子串出現在多少個文本串中，這個可以用set啟發式合并查詢出來，求本質不同的子串的數目也就是\(\sum_{u=1}^{tot}{node[u].len-node[fa].len}\)那么我們也就只要篩選出哪些節點滿足條件然后求個和就好了

tips

我自己寫了個奇怪做法，就是在啟發式合并的時候，如果這個點的\(size()==1\)我們也就記錄一下這一個是什么，因為，在啟發式合并的時候，set[v]會被修改

#include<bits/stdc++.h> #include<set> using namespace std; const int maxn=200010; inline int read(){int w=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=(w<<3)+(w<<1)+ch-48;ch=getchar();}return w*f; } int n,m; bool debug; set<int> s[maxn]; set<int>::iterator it; struct SUFFIXAUTOMATON{struct Node{int len,fa;map<int,int> ch;}node[200010];int lst,tot,root;inline void init(){lst=tot=root=1;return;}inline void extend(int now,int id){int p=lst;tot++;lst=tot;int np=tot;node[np].len=node[p].len+1;s[np].insert(id);while(p&&!node[p].ch[now]){node[p].ch[now]=np;p=node[p].fa;}if(!p) node[np].fa=1;else{int q=node[p].ch[now];if(node[q].len==node[p].len+1){node[np].fa=q;}else{int nq=++tot;node[nq]=node[q];node[nq].len=node[p].len+1;node[q].fa=nq;node[np].fa=nq;while(p&&node[p].ch[now]==q){node[p].ch[now]=nq;p=node[p].fa;}}}} }SAM; string ch[200010]; int cnt,head[200010],sum[200010]; int id[200010]; struct Edge{int from,to,next; }edge[1200010]; inline void addedge(int u,int v){cnt++;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];head[u]=cnt; } inline void dfs(int u){for(int i=head[u];i;i=edge[i].next){int v=edge[i].to;dfs(v);if(s[u].size()<s[v].size()) swap(s[u],s[v]);for(it=s[v].begin();it!=s[v].end();it++){s[u].insert(*it);}}sum[u]=s[u].size();if(sum[u]==1){it=s[u].begin();id[u]=*it;} } int ans[200010]; int main(){n=read();SAM.init();for(int i=1;i<=n;i++){cin>>ch[i];int len=ch[i].length();for(int j=0;j<len;j++){SAM.extend(ch[i][j]-'a'+1,i);}SAM.lst=1;}for(int i=2;i<=SAM.tot;i++){addedge(SAM.node[i].fa,i);}dfs(1);//debug=true;if(debug){for(int i=1;i<=SAM.tot;i++){for(int j=1;j<=26;j++){if(SAM.node[i].ch[j]){cout<<i<<" "<<SAM.node[i].ch[j]<<" "<<(char)('a'+j-1)<<endl;}}}}if(debug){for(int i=1;i<=SAM.tot;i++){cout<<i<<" "<<id[i]<<endl;}}for(int u=1;u<=SAM.tot;u++){if(sum[u]!=1) continue;int f=SAM.node[u].fa;ans[id[u]]+=SAM.node[u].len-SAM.node[f].len;}for(int i=1;i<=n;i++){printf("%d\n",ans[i]);}if(debug){int cur=0;for(int i=1;i<=SAM.tot;i++){int f=SAM.node[i].fa;cur+=SAM.node[i].len-SAM.node[f].len;}cout<<cur<<endl;}return 0; }

轉載于:https://www.cnblogs.com/wenci/p/10631796.html

總結

以上是生活随笔為你收集整理的BZOJ5137lg4081(广义后缀自动机，set启发式合并)的全部內容，希望文章能夠幫你解決所遇到的問題。

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