洛谷P7537-字典树+DFS

 题目链接：

题目链接

 题目大意： 

求一个序列，使得序列中相邻两个字符串押韵。

押韵解释为： 字符串A与B的最长公共后缀LCS(A,B)≥max⁡(∣A∣,∣B∣)−1。 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int N=3000050;//3000050
set<int>v[3000050];
int trie[N][27]={0};
int num[N]={0};//结尾
int getnum(char x){
	return x-'a';
}
int cnt=0;
int ans=1;//至少有一个
int f[3000050]={0};//每个节点的最长链
void dfs(int rt){
	int maxn=0,big=0,kids=0;//kids指有效儿子
	// 最长链+次长链
	for(int i=0;i<26;i++){
		if(!trie[rt][i]) {
			continue;
		}
		int y=trie[rt][i];//能往下走
		kids+=num[y];//加有效儿子数
		dfs(y);//往下走
		if(maxn<f[y]){
			big=maxn;maxn=f[y];//最大值更新
		}else{
			big=max(big,f[y]);//次大值更新
		}
	}
	ans=max(ans,num[rt]+maxn+big+max(kids-2,0));h
	//以这个节点结尾的单词+以它开始的最长链+次长链+所有有效儿子
	//因为最长链和次长链包含两个有效儿子，所以有效儿子从kids-2算
	if(num[rt]==0){
		f[rt]=0;//这个节点没有结尾的;从他开始的最长链断掉。
	}else{
		f[rt]=maxn+max(kids-1,0)+num[rt];
		//能接上，f[rt]=它所有儿子中那个最长链+有效儿子+以它结尾的单词
		//因为最长链包含一个儿子，所以kids从kids-1算
	}
}
int main(){
	int n=0;scanf("%d",&n);
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		int p=0;
		for(int j=s.length()-1;j>=0;j--){
			int x=getnum(s[j]);
			if(!trie[p][x]) trie[p][x]=++cnt;
			v[p].insert(trie[p][x]);
			p=trie[p][x];
			if(j==0)num[p]++;
		}
	}
	dfs(0);//root
	printf("%d",ans);
	
	return 0;	
}