題目鏈接：點擊查看
題目大意：給出一個大小為 n 的字符串集記為 X，給出兩個字符串相似的定義為：如果某個字符串去掉首字母可以得到另一個字符串
現在需要構造一個盡可能大的字符串集，滿足以下兩個條件：
所有的元素都是 X 中元素的前綴任意兩個元素都不能相似
題目分析：因為需要構造的字符串集內的元素都是前綴，不難想到字典樹，再考慮如果兩個字符串是相似的，在字典樹上的表現為：一個串是另一個串的 fail ，且深度恰好相差?1 。回想一下 fail 指針的定義，也就是與前綴匹配的最長后綴，所以如果 fail 指針指向的節點所代表的元素為當前元素的后綴，且深度（也就是字符串長度）相差恰好為 1 的話，那么便符合了 “相似” 的條件，更確切的說，這兩個前綴無法同時被選中
所以我們可以給符合上述條件的 fail 指針建邊，這樣最后得到的是一棵森林，因為并不是每一個 fail 指針都會連邊，在新建出來的 fail 森林上用樹形 dp 跑 “樹上最大獨立集” 便是答案了
代碼：
?
//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e6+100;vector<int>node[N];char s[N];int fail[N],trie[N][26],deep[N],dp[N][2],cnt;bool vis[N];int newnode()
{cnt++;for(int i=0;i<26;i++)trie[cnt][i]=0;return cnt;
}void insert_word()
{int len=strlen(s+1);int pos=0;for(int i=1;i<=len;i++){int to=s[i]-'a';if(!trie[pos][to]){trie[pos][to]=newnode();deep[trie[pos][to]]=i;}pos=trie[pos][to];}
}void getfail()
{queue<int>q;for(int i=0;i<26;i++){if(trie[0][i]){fail[trie[0][i]]=0;q.push(trie[0][i]);}}while(!q.empty()){int cur=q.front();q.pop();for(int i=0;i<26;i++){if(trie[cur][i]){fail[trie[cur][i]]=trie[fail[cur]][i];q.push(trie[cur][i]);}elsetrie[cur][i]=trie[fail[cur]][i];}}
}void build()
{for(int i=1;i<=cnt;i++)node[i].clear();for(int i=1;i<=cnt;i++)if(fail[i]&&deep[fail[i]]+1==deep[i]){node[fail[i]].push_back(i);node[i].push_back(fail[i]);}
}void dfs(int u,int fa)
{vis[u]=true;dp[u][0]=0,dp[u][1]=1;for(auto v:node[u]){if(v==fa)continue;dfs(v,u);dp[u][0]+=max(dp[v][0],dp[v][1]);dp[u][1]+=dp[v][0];}
}void init()
{cnt=-1;newnode();
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){init();int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%s",s+1);insert_word();}getfail();build();int ans=0;memset(vis,false,cnt+5);for(int i=1;i<=cnt;i++)if(!vis[i]){dfs(i,-1);ans+=max(dp[i][0],dp[i][1]);}printf("%d\n",ans);}return 0;
}
?
總結
以上是生活随笔為你收集整理的CodeForces - 856B Similar Words(AC自动机+树形dp)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
