洛谷 P4471 [BJWC2018]词韵 (字典树）

题目链接：https://www.luogu.org/problemnew/show/P4471

题目描述

Adrian 很喜欢诗歌中的韵。他认为，两个单词押韵当且仅当它们的最长公共后缀的长度至少是其中较长单词的长度减一。也就是说，单词A 与单词B 押韵当且仅当LCS(A,B) ≥ max(|A|,|B|)- 1。( 其中LCS 是最长公共后缀longest common suffix 的缩写）

现在， Adrian 得到了N 个单词。他想从中选出尽可能多的单词，要求它们能组成一个单词序列，使得单词序列中任何两个相邻单词是押韵的。

输入输出格式

输入格式：

 

第一行是一个整数N。

接下来N 行，每行一个由小写英文字母组成的字符串，表示每个单词。所有单词互不相同。

 

输出格式：

 

输出一行，为一个整数， 表示最长单词序列的长度。

 

输入输出样例

输入样例#1： 复制

5
ask
psk
k
krafna
sk

输出样例#1： 复制

4

说明

【样例解释】

一种最长单词序列是ask-psk-sk-k。

【数据规模和约定】

30%的测试数据：1≤N≤20，所有单词长度之和不超过3 000

100%的测试数据：1≤N≤500000，所有单词长度之和不超过3 000 000。

 

思路：将字符串翻转建立字典树。然后分两种情况去考虑下：①就是寻找最长的单链 ② 找2个最长的子链加上本身拼接。

以下所说的节点都是储存单词结尾的节点 这样的点才是有用的点

① 对于叶子节点 他得贡献肯定的自己本身的单词的出现次数也就是valu[i]，对于他的父亲，假如只有一个儿子的话，那么他的到的贡献肯定是等于valu[儿子]+valu[自己] ,如果有多个儿子的话，可选择2个拥有最长链的儿子拼成一个。

valu[父亲]=valu[父亲]+valu[max]+valu[max1]。

画的丑了点  大概的意思可以组成一个 abc->ab->a->ac->acd 这样的一个链也是满足题意的。最后就变成了单链和合并2个孩子求一个max即可。

我表达能力一般 可以参考下：https://blog.csdn.net/winter2121/article/details/81213624 

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
char s[maxn];
int head[maxn];
int valu[maxn];
int dp[maxn],dp1[maxn]; 
int cnt;
struct node{
	char c;
	int to;
}no[maxn];
void add(int root,char s)
{ 
	no[++cnt].c=s;
	no[cnt].to=head[root];
	head[root]=cnt;
}
void insert(char *s)//链式前向星的简历字典树 NB 
{
	int root=0; 
	int len = strlen(s);
	for(int i=0;i<len;i++)
	{
		int flag=1;
		for(int j=head[root];j!=-1;j=no[j].to)
		{
			if(s[i] == no[j].c)
			{
				flag=0;
				root=j;
				break;
			}
		}
		if(flag)
		{
			add(root,s[i]);
			root=cnt;
		}
	} 
	valu[root]++;//单词的数量 
}
void dfs(int root)
{//叶子节点就是valu[i]   
	int Valu[2]={0,0};
	int flag=0;//标记点 
	for(int i=head[root];i!=-1;i=no[i].to)
	{
		dfs(i);//递归到最下 
		//Valu数组的作用就是求root的孙子辈最长的一个链 然后串起来他所有儿子 
		int Mc=dp1[i] - valu[i];
		if(Mc > Valu[1])
		{
			Valu[0]=Valu[1];
			Valu[1]=Mc;
		}
		else if(Mc > Valu[0])
			Valu[0] = Mc;
		flag = flag + valu[i];
	}
	 
	flag = flag +valu[root]; 
	if(Valu[0]>0)//连接2个孩子 
		dp[root] = Valu[0] + Valu[1] + flag;
		
	if(valu[root])//如果当前点是一个单词的结束； 如果是跟的话  dp[root]就等于 valu[root]
		dp1[root]= flag + Valu[1];//不是的话就加上最长的那个链 
}
int main()
{
	memset(head,-1,sizeof(head));
	int n;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%s",s);
		int len = strlen(s);
		for(int i=0;i<len/2;i++)
			swap(s[i],s[len-i-1]);
		insert(s);
	}
	dfs(0);
	int Ans=0;
	for(int i=0;i<=cnt;i++)
		Ans=max(Ans,max(dp[i],dp1[i]));
	printf("%d\n",Ans);
	return 0;
}