本文主要是介绍【Trie树】模板题-POJ-2001，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你若干个单词，写出能每个单词的最短前缀
也就是说这个前缀能准确代表这个单词，和其他单词 without ambiguity
思路：
建立字典树存下这几个单词，ct 数组记录每个节点的子节点数，显然子树宽度只有1的话，这个单词就被确定了，改造一下我们的 find_word 函数就行啦
哦。。这个结构体要怎么搞还坑了我一下，要向下面那样定义！
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;const int maxnode = 20050;
const int sigma_size = 30;char str[1050][25];///字母表为全体小写字母的 Trie
struct Trie
{int ch[maxnode][sigma_size];int val[maxnode];int ct[maxnode];int sz; ///节点总数Trie() { sz = 1; memset(ch[0],0,sizeof(ch[0])); memset(ct,0,sizeof(ct)); } ///初始时只有一个根节点int idx (char c) { return c - 'a'; } ///字符c的编号///插入字符串 s, 附加信息为 v。 注意 v 必须非0，因为 0 代表“本节点不是单词节点”void insert_word(char *s,int v){int u = 0, n = strlen(s);for(int i=0; i<n; i++){ct[u]++;int c = idx(s[i]);if(!ch[u][c]) {memset(ch[sz],0,sizeof(ch[sz]));val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}val[u] = v;ct[u]++;}void find_word(char *s){int u = 0, n = strlen(s);for(int i=0; i<n; i++){int c = idx(s[i]);printf("%c",s[i]);u = ch[u][c];if(ct[u] == 1)break;}printf("\n");}
}my_trie;int main()
{freopen("input.txt","r",stdin);int top = 0;while(scanf("%s",str[top]) != EOF){//cout<<str[top]<<endl;my_trie.insert_word(str[top],1);top++;}for(int i=0;i<top;i++){printf("%s ",str[i]);my_trie.find_word(str[i]);}return 0;
}
这篇关于【Trie树】模板题-POJ-2001的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
