题目链接：https://www.luogu.com.cn/problem/P1481
题意
- 给你n个单词。
- 如果在一个由一个词或多个词组成的表中，除了最后一个以外，每个单词都被其后的一个单词所包含，即前一个单词是后一个单词的前缀，则称词表为一个词链。
- 求最长词链所包含的单词数。
- 字典树模板题。
- 插入完了过后求一下经过的总的字符串个数，并更新其最大值
#include
using namespace std;
const int N = 2020;
struct node{
int next[27];
//下一个字符位置
int num;
//代表以当前字母为结尾的单词在树中出现多少次
int ans,tot;
void add_node(string s){
int len=s.size(),pos=0;
int res=0;
for(int i=0;
i>n;
for(int i=1;
i<=n;
i++){
string s;
cin>>s;
add_node(s);
}
cout< 链表篇
#include
using namespace std;
struct node{
int num=0;
//代表以当前字母为结尾的单词在树中出现多少次
int flag=0;
//标记，看是不是最后一个字母
node *next[27];
};
int ans;
//建树初始化
node* creat(){
node *root = new node();
root->flag=0;
root->num=0;
memset(root->next,NULL,sizeof(root->next));
return root;
}//插入一个单词
void insert(node *root,char *word){
int res=0;
node *location=root;
while(*word){
if(location->next[*word-'a']==NULL){
node *tmp=creat();
location->next[*word-'a']=tmp;
}
location=location->next[*word-'a'];
word++;
if(location->num)res+=location->num;
//location->num++;
}
location->num++;
ans=max(ans,res+location->num);
}//查询关键词出现的次数
int search(node *root,char *word){
node *location=root;
while(location && *word){
location = location -> next[*word-'a'];
word++;
}
if(location && location->flag)return location->num;
else{
cout<<"error"<next[i]){
Delete(root->next[i]);
}
}
delete root;
}
int main(){
int n;
cin>>n;
node *root=creat();
for(int i=1;
i<=n;
i++){
char s[1005];
cin>>s;
insert(root,s);
}
cout< 【P1481 魔族密码 （字典树 模板）】
