from:https://www.cnblogs.com/justinh/p/7716421.HTML
TrIE，又经常叫前缀树，字典树等等。它有很多变种，如后缀树，Radix Tree/TrIE，PATRICIA tree，以及bitwise版本的crit-bit tree。当然很多名字的意义其实有交叉。
定义
在计算机科学中，trIE，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。
trIE中的键通常是字符串，但也可以是其它的结构。trIE的算法可以很容易地修改为处理其它结构的有序序列，比如一串数字或者形状的排列。比如，bitwise trIE中的键是一串位元，可以用于表示整数或者内存地址
基本性质
1，根节点不包含字符，除根节点意外每个节点只包含一个字符。
2，从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
3，每个节点的所有子节点包含的字符串不相同。
优点：
可以最大限度地减少无谓的字符串比较，故可以用于词频统计和大量字符串排序。
跟哈希表比较：
1，最坏情况时间复杂度比hash表好
2，没有冲突，除非一个key对应多个值（除key外的其他信息）
3，自带排序功能（类似Radix Sort），先序遍历trIE可以得到排序。
缺点：1，虽然不同单词共享前缀，但其实trIE是一个以空间换时间的算法。其每一个字符都可能包含至多字符集大小数目的指针（不包含卫星数据）。
每个结点的子树的根节点的组织方式有几种。1>如果默认包含所有字符集，则查找速度快但浪费空间（特别是靠近树底部叶子）。2>如果用链接法(如左儿子右兄弟)，则节省空间但查找需顺序（部分）遍历链表。3>Alphabet reduction: 减少字符宽度以减少字母集个数。,4>对字符集使用bitmap，再配合链接法。
2，如果数据存储在外部存储器等较慢位置，TrIE会较hash速度慢（hash访问O(1)次外存，TrIE访问O(树高)）。
3，长的浮点数等会让链变得很长。可用bitwise trIE改进。
bit-wise TrIE
类似于普通的TrIE，但是字符集为一个bit位，所以孩子也只有两个。
可用于地址分配，路由管理等。
虽然是按bit位存储和判断，但因为cache-local和可高度并行，所以性能很高。跟红黑树比，红黑树虽然纸面性能更高，但是因为cache不友好和串行运行多，瓶颈在存储访问延迟而不是cpu速度。
压缩TrIE
压缩分支条件：
1，TrIE基本不变
2，只是查询
3，key跟结点的特定数据无关
4，分支很稀疏
若允许添加和删除，就可能需要分裂和合并结点。此时可能需要对压缩率和更新（裂，并）频率进行折中。
外存TrIE
某些变种如后缀树适合存储在外部，另外还有B-trIE等。
应用场景：
（1） 字符串检索
事先将已知的一些字符串（字典）的有关信息保存到trIE树里，查找另外一些未知字符串是否出现过或者出现频率。
举例：
1，给出N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，请你按最早出现的顺序写出所有不在熟词表中的生词。
2，给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，若rob是不良单词，那么文本problem含有不良单词。
3，1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。
（2）文本预测、自动完成，see also，拼写检查
（3）词频统计
1，有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
2，一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
3，寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复度比较高，虽然总数是1千万，但是如果去除重复，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。
(1) 请描述你解决这个问题的思路；
(2) 请给出主要的处理流程，算法，以及算法的复杂度。
==》若无内存限制：TrIE + “k-大/小根堆”（k为要找到的数目）。
否则，先hash分段再对每一个段用hash（另一个hash函数）统计词频，再要么利用归并排序的某些特性（如partial_sort），要么利用某使用外存的方法。参考
“@L_502_0@” http://www.dataguru.cn/thread-485388-1-1.html。
“算法面试题之统计词频前k大” http://www.voidcn.com/article/p-hdntczgk-bco.html
算法导论笔记——第九章 中位数和顺序统计量
（4）排序
TrIE树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串便是按字典序排序的结果。
比如给你N 个互不相同的仅由一个单词构成的英文名，让你将它们按字典序从小到大排序输出。
（5）字符串最长公共前缀
TrIE树利用多个字符串的公共前缀来节省存储空间，当我们把大量字符串存储到一棵trIE树上时，我们可以快速得到某些字符串的公共前缀。
举例：
给出N 个小写英文字母串，以及Q 个询问，即询问某两个串的最长公共前缀的长度是多少？
解决方案：首先对所有的串建立其对应的字母树。此时发现，对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数，于是，问题就转化为了离线（Offline）的最近公共祖先（Least Common Ancestor，简称LCA）问题。
而最近公共祖先问题同样是一个经典问题，可以用下面几种方法：
1. 利用并查集（disjoint Set），可以采用采用经典的Tarjan 算法；
2. 求出字母树的欧拉序列（Euler Sequence ）后，就可以转为经典的最小值查询（Range Minimum query，简称RMQ）问题了；
（6）字符串搜索的前缀匹配
trIE树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。
TrIE树检索的时间复杂度可以做到n，n是要检索单词的长度，
如果使用暴力检索，需要指数级O(n2)的时间复杂度。
（7） 作为其他数据结构和算法的辅助结构
如后缀树，AC自动机等
后缀树可以用于全文搜索
转一篇关于几种TrIE速度比较的文章：http://www.hankcs.com/nlp/performance-comparison-of-several-trie-tree.html
TrIE树和其它数据结构的比较 http://www.raychase.net/1783
参考：
[1] 维基百科：TrIE， https://en.wikipedia.org/wiki/Trie
[2] LeetCode字典树(TrIE)总结， http://www.jianshu.com/p/bbfe4874f66f
[3] 字典树(TrIE树)的实现及应用， http://www.cnblogs.com/binyue/p/3771040.html#undefined
[4] 6天通吃树结构—— 第五天 TrIE树， http://www.cnblogs.com/huangxincheng/archive/2012/11/25/2788268.html
在TrIE树中主要有3个 *** 作，插入、查找和删除。一般情况下TrIE树中很少存在删除单独某个结点的情况，因此只考虑删除整棵树。
例题及思路
统计难题HDU1251
Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀). input输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample inputbananabandbeeabsoluteacmbabbandabc Sample Output 2310
统计出以某个字符串为前缀的单词数量，首先构建出trIE树并记录每个节点的访问次数，然后在上面查询就好了，模板题。
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #define MAXN 26 6 using namespace std; 7 8 struct TrIE 9 {10 TrIE *Next[MAXN];11 int Flag;12 TrIE()13 {14 Flag=1;15 memset(Next,NulL,sizeof(Next));16 }17 };18 19 struct TrIE* Root;20 21 voID Insert(char* str)22 {23 TrIE *p,*q;24 p=Root;25 int len=strlen(str);26 for(int i=0;i<len;++i)27 {28 int key=str[i]-‘a‘;29 if(p->Next[key]==NulL)30 {31 q=new TrIE();32 p->Next[key]=q;33 p=p->Next[key];34 }35 else 36 {37 p=p->Next[key];38 ++p->Flag;39 }40 }41 }42 43 int Qurey(char *str)44 {45 int len=strlen(str);46 TrIE* p=Root;47 for(int i=0;i<len;++i)48 {49 int key=str[i]-‘a‘;50 if(p->Next[key]==NulL)51 return 0;52 p=p->Next[key];53 }54 return p->Flag;55 56 }57 58 voID Free(TrIE* T)59 {60 if(T==NulL) return;61 for(int i=0;i<MAXN;i++)62 {63 if(T->Next[i]) Free(T->Next[i]);64 }65 delete(T);66 }67 68 int main()69 {70 //freopen("sample.txt","r",stdin);71 char str[15];72 Root=new TrIE();73 while(*gets(str)) //效果等同于while(gets(str)&&str[0]!=0)74 {75 Insert(str);76 }77 while(~scanf("%s",str))78 {79 printf("%d\n",Qurey(str));80 }81 Free(Root);82 return 0;83 }
单词数
HDU2072
Problem Descriptionlily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。
input有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。
Output每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。
Sample inputyou are my frIEnd# Sample Output 4
统计出现的不同单词的个数，直接把字符全部插入TrIE树中，然后遍历trIE树，统计所有具有End标记的节点个数就好了。
提示：多样例输入的格式是第一种，用字符数组会被卡
这里可以用 istringstream来快速从字符串中根据空格来提取单词，istringstream对象可以绑定一行字符串，然后以空格为分隔符把该行分隔开来。(要加头文件sstream)
1 #include <cstdio> 2 #include <iostream> 3 #include <cstring> 4 #include <algorithm> 5 #include <sstream> 6 #define MAXN 26 7 using namespace std; 8 9 struct TrIE10 {11 TrIE *Next[MAXN];12 int flag;13 int end;14 TrIE()15 {16 flag=1;17 end=0;18 memset(Next,sizeof(Next));19 }20 }*Root;21 22 voID Insert(string str)23 {24 TrIE *p=Root;25 TrIE *q;26 int len=str.size();27 for(int i=0;i<len;++i)28 {29 int key=str[i]-‘a‘;30 if(p->Next[key]==NulL)31 {32 q=new TrIE();33 p->Next[key]=q;34 p=p->Next[key];35 }36 else 37 {38 p=p->Next[key];39 ++p->flag;40 }41 if(i==len-1)42 p->end=1;43 }44 }45 46 int visit(TrIE* T,int &sum) //遍历trIE树47 {48 if(T==NulL)49 return 0;50 if(T->end==1)51 sum++;52 for(int i=0;i<MAXN;i++)53 {54 visit(T->Next[i],sum);55 }56 }57 58 voID Free(TrIE* T)59 {60 if(T==NulL) return;61 for(int i=0;i<MAXN;i++)62 {63 if(T->Next[i]) Free(T->Next[i]);64 }65 delete(T);66 }67 68 int main()69 {70 string str;71 string tem; //字符数组被卡，改用string就过了。。。。72 int sum=0;73 Root=new TrIE();74 while(getline(cin,str)&&str!="#")75 {76 istringstream is(str); //is相当于存单词的一个容器77 while(is>>tem) //将is中的字符串依次赋给string78 {79 Insert(tem);80 }81 visit(Root,sum);82 printf("%d\n",sum);83 Free(Root);84 Root=new TrIE();85 sum=0;86 }87 Free(Root);88 return 0;89 }
Shortest Prefixes
POJ2001
Description A prefix of a string is a substring starting at the beginning of the given string. The prefixes of "carbon" are: "c","ca","car","carb","carbo",and "carbon". Note that the empty string is not consIDered a prefix in this problem,but every non-empty string is consIDered to be a prefix of itself. In everyday language,we tend to abbreviate words by prefixes. For example,"carbohydrate" is commonly abbreviated by "carb". In this problem,given a set of words,you will find for each word the shortest prefix that uniquely IDentifIEs the word it represents.In the sample input below,"carbohydrate" can be abbreviated to "carboh",but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the List that begin with "carbo".
An exact match will overrIDe a prefix match. For example,the prefix "car" matches the given word "car" exactly. Therefore,it is understood without ambiguity that "car" is an abbreviation for "car",not for "carriage" or any of the other words in the List that begins with "car". input The input contains at least two,but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters. Output The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input,followed by one blank space,and the shortest prefix that uniquely (without ambiguity) IDentifIEs this word. Sample input
carbohydratecartcarburetorcaramelcariboucarboniccartilagecarboncarriagecartoncarcarbonate Sample Output carbohydrate carbohcart cartcarburetor carbucaramel caracaribou caricarbonic carbonicartilage carticarbon carboncarriage carrcarton cartocar carcarbonate carbona 求一个能代表这个字符串的最短前缀，也就是只有这个字符串具有的前缀，否则输出这个字符串本身
做法很显然，先构建好TrIE树，然后对每个单词进行find，递归到直到节点出现次数为1，表示这个节点只有这一个单词走过，返回就ok。
这里可以用string不断拼接字符，然后直接返回，减少一些代码量。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 #define MAXN 26 7 const int maxn=2e6+5; 8 int TrIE[maxn][MAXN]; 9 int Count[maxn];10 bool End[maxn];11 int tot;12 13 voID Find(char *str)14 {15 int len=strlen(str);16 int Root=0;17 int flag=1;18 int i;19 for(i=0;i<len;i++)20 {21 int key=str[i]-‘a‘;22 Root=TrIE[Root][key];23 printf("%c",str[i]);24 if(Count[Root]==1)25 {26 printf("\n");27 return;28 } 29 }30 printf("\n");31 return ;32 }33 34 voID Insert(char *str)35 {36 int len=strlen(str);37 int Root=0;38 for(int i=0;i<len;i++)39 {40 int key=str[i]-‘a‘;41 if(!TrIE[Root][key])42 {43 TrIE[Root][key]=++tot;44 Count[TrIE[Root][key]]=1;45 }46 else47 {48 Count[TrIE[Root][key]]++;49 } 50 Root=TrIE[Root][key];51 }52 End[Root]=true;53 }54 55 voID init()56 {57 for(int i=0;i<tot;i++)58 {59 End[i]=false;60 Count[i]=0;61 for(int j=0;j<MAXN;j++)62 {63 TrIE[i][j]=0;64 }65 }66 tot=0;67 }68 char ss[1005][21];69 int main()70 {71 int num=0;72 while(scanf("%s",ss[num])!=EOF)73 {74 Insert(ss[num++]);75 }76 for(int i=0;i<num;i++)77 {78 printf("%s ",ss[i]);79 Find(ss[i]);80 }81 init();82 return 0;83 }
Phone List
POJ3630
DescriptionGiven a List of phone numbers,determine if it is consistent in the sense that no number is the prefix of another. Let‘s say the phone catalogue Listed these numbers:
Emergency 911 Alice 97 625 999 Bob 91 12 54 26In this case,it‘s not possible to call Bob,because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob‘s phone number. So this List would not be consistent.
inputThe first line of input gives a single integer,1 ≤ t ≤ 40,the number of test cases. Each test case starts with n,the number of phone numbers,on a separate line,1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.
OutputFor each test case,output "YES" if the List is consistent,or "NO" otherwise.
Sample input2391197625999911254265113123401234401234598346Sample Output
NOYES 给出一个字符串集合，问是否所有的字符串都不是其他字符串的前缀，
如果字符串Xn=X1X2....Xn是字符串Ym=Y1Y2....Ym的前缀，有在插入的时候有两种情况:Xn在Yn之前插入，Xn在Yn之后插入。 1)如果Xn在Yn之前插入，那么在插入Yn的时候必然经过Xn的路径，此时可以根据判断在这条路径上是否已经有结点被标记已经构成完成的字符串序列来判断是否存在Yn的前缀； 2)如果Xn在Yn之后插入，那么插入完成之后当前指针指向的结点的next数组中的元素必定不全为NulL或0。之前一直时间超限。。。。把链式结构换成了二维数组
然后这个竟然wa掉了，
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 #define MAXN 10 7 const int maxn=2e6+5; 8 int TrIE[maxn][MAXN]; 9 bool End[maxn];10 int tot;11 12 voID init()13 {14 for(int i=0;i<tot;i++)15 {16 End[i]=false;17 for(int j=0;j<MAXN;j++)18 {19 TrIE[i][j]=0;20 }21 }22 tot=0;23 }24 25 int main()26 {27 int t;28 scanf("%d",&t);29 while(t--)30 {31 int n;32 scanf("%d",&n);33 getchar();34 int flag=1; 35 while(n--)36 {37 char str[20];38 gets(str);39 int len=strlen(str);40 int Root=0;41 for(int i=0;i<len;i++)42 {43 int key=str[i]-‘0‘;44 if(!TrIE[Root][key])45 TrIE[Root][key]=++tot;46 else if(End[TrIE[Root][key]]==true)47 {48 flag=0;49 }50 Root=TrIE[Root][key];51 if(i==len-1)52 End[Root]=true;53 }54 for(int i=0;i<MAXN;i++)55 {56 if(TrIE[Root][i]!=0)57 {58 flag=0;59 break;60 }61 }62 }63 if(flag)64 printf("YES\n");65 else 66 printf("NO\n");67 init();68 }69 return 0;70 }
能过的代码：
首先构造出TrIE树，然后对每个字符串find，当find的路径上如果出现其他字符串结尾标记，就说明其他字符串是当前字符串的前缀。注意这里对每个字符串find的时候只要搜索到len−1 len-1len−1即可，如果搜索到len lenlen，那么将会将本身的字符串统计进去。
1 #include<stdio.h> 2 #include<iostream> 3 #include<string.h> 4 using namespace std; 5 const int maxn =2e6+5; 6 int tree[maxn][15]; 7 bool flagg[maxn]; 8 int tot; 9 voID insert_(char *str)10 {11 int len=strlen(str);12 int root=0;13 for(int i=0;i<len;i++)14 {15 int ID=str[i]-‘0‘;16 if(!tree[root][ID]) tree[root][ID]=++tot;17 root=tree[root][ID];18 }19 flagg[root]=true;20 }21 int find_(char *str)22 {23 int len=strlen(str);24 int root=0;25 for(int i=0;i<len-1;i++)26 {27 int ID=str[i]-‘0‘;28 root=tree[root][ID];29 if(flagg[root]) return true;//路径上出现过其他字符串的结尾标记30 }31 return false;32 }33 char ss[10005][12];34 int main()35 {36 int n,t;37 scanf("%d",&t);38 while(t--)39 {40 scanf("%d",&n);41 for(int i=0;i<n;i++)42 {43 scanf("%s",ss[i]);44 insert_(ss[i]);45 }46 int flag=0;47 for(int i=0;i<n;i++)48 {49 if(find_(ss[i]))50 {51 flag=1;52 break;53 }54 }55 if(flag==0)56 printf("YES\n");57 else58 printf("NO\n");59 for(int i=0;i<=tot;i++)60 {61 flagg[i]=false;62 for(int j=0;j<10;j++)63 tree[i][j]=0;64 }65 tot=0;66 }67 return 0;68 }69 --------------------- 70 作者：lajiyuan_ 71 来源：CSDN 72 原文：https://blog.csdn.net/qq_38891827/article/details/80532462 73 版权声明：本文为博主原创文章，转载请附上博文链接！
T9
POJ1451
Description BackgroundA while ago it was quite cumbersome to create a message for the Short Message Service (SMS) on a mobile phone. This was because you only have nine keys and the Alphabet has more than nine letters,so most characters Could only be entered by pressing one key several times. For example,if you wanted to type "hello" you had to press key 4 twice,key 3 twice,key 5 three times,again key 5 three times,and finally key 6 three times. This procedure is very tedious and keeps many people from using the Short Message Service.
This led manufacturers of mobile phones to try and find an easIEr way to enter text on a mobile phone. The solution they developed is called T9 text input. The "9" in the name means that you can enter almost arbitrary words with just nine keys and without pressing them more than once per character. The IDea of the solution is that you simply start tyPing the keys without repetition,and the software uses a built-in dictionary to look for the "most probable" word matching the input. For example,to enter "hello" you simply press keys 4,3,5,and 6 once. Of course,this Could also be the input for the word "gdjjm",but since this is no sensible English word,it can safely be ignored. By ruling out all other "improbable" solutions and only taking proper English words into account,this method can speed up writing of short messages consIDerably. Of course,if the word is not in the dictionary (like a name) then it has to be typed in manually using key repetition again. figure 8: The Number-keys of a mobile phone.
More precisely,with every character typed,the phone will show the most probable combination of characters it has found up to that point. Let us assume that the phone kNows about the words "IDea" and "hello",with "IDea" occurring more often. Pressing the keys 4,and 6,one after the other,the phone offers you "i","ID",then switches to "hel","hell",and finally shows "hello".
Problem
Write an implementation of the T9 text input which offers the most probable character combination after every keystroke. The probability of a character combination is defined to be the sum of the probabilitIEs of all words in the dictionary that begin with this character combination. For example,if the dictionary contains three words "hell","hello",and "hellfire",the probability of the character combination "hell" is the sum of the probabilitIEs of these words. If some combinations have the same probability,your program is to select the first one in Alphabetic order. The user should also be able to type the beginning of words. For example,if the word "hello" is in the dictionary,the user can also enter the word "he" by pressing the keys 4 and 3 even if this word is not Listed in the dictionary.
The first line contains the number of scenarios.
Each scenario begins with a line containing the number w of distinct words in the dictionary (0<=w<=1000). These words are given in the next w lines. (They are not guaranteed in ascending Alphabetic order,although it‘s a dictionary.) Every line starts with the word which is a sequence of lowercase letters from the Alphabet without whitespace,followed by a space and an integer p,1<=p<=100,representing the probability of that word. No word will contain more than 100 letters.
Following the dictionary,there is a line containing a single integer m. Next follow m lines,each consisting of a sequence of at most 100 decimal digits 2-9,followed by a single 1 meaning "next word".
The output for each scenario begins with a line containing "Scenario #i:",where i is the number of the scenario starting at 1.
For every number sequence s of the scenario,print one line for every keystroke stored in s,except for the 1 at the end. In this line,print the most probable word prefix defined by the probabilitIEs in the dictionary and the T9 selection rules explained above. Whenever none of the words in the dictionary match the given number sequence,print "MANUALLY" instead of a prefix.
Terminate the output for every number sequence with a blank line,and print an additional blank line at the end of every scenario.
25hell 3hello 4IDea 8next 8super 32435561433217another 5contest 6follow 3give 13integer 6new 14program 4577647261639146812668437177771Sample Output
Scenario #1:iIDhelhellhelloiIDIDeIDeaScenario #2:pprproprogprogrprograprogramnnenewginintccoconcontanothanotheanotherpprMANUALLYMANUALLY
Hat’s Words
HDU1247
Problem Description A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.You are to find all the hat’s words in a dictionary. input Standard input consists of a number of lowercase words,one per line,in Alphabetical order. There will be no more than 50,000 words.
Only one case. Output Your output should contain all the hat’s words,in Alphabetical order. Sample input
aahathathatwordhzIEeword Sample Output ahathatword
给出n个按字典序排列的单词，问其中的所有能由另外两个单词组成的单词并按字典序输出
(推荐)思路1：先建好字典树，然后枚举一个单词将其拆分成两个单词并查询字典树中是否有这两个单词；
思路2：先把所有的单词构造成一颗trIE图，然后对所有的单词进行枚举，在trIE图上面判断一个单词是否由其它两个单词构成，具有的做法是先沿着路径一直走，如果走到某个节点，该节点为一个单词的结尾，那么再对剩余的单词再从trIE图的根开始遍历，看是否能和一个单词匹配，若匹配成功则该单词满足要求，否则继续进行匹配...
思路3：可以建两颗TrIE树，然后分别正序倒序插入每个单词，对每个单词查询的时候，分别正序倒序查询，对出现过单词的前缀下标进行标记，对每个出现过单词的后缀进行标记，最后扫描标记数组，如果某个位置前缀后缀均被标记过，则表示可以拆成单词表中的两个其他单词。
没有想到该怎样枚举，只想选一个单词另外两个怎么选，该弄多少个循环呀，看了别人的方法才知道将这个单词拆分成两个单词；还了解了strncpy，一些字符函数能用则用，本来就是为了方便！
1 #include <cstdio> 2 #include <iostream> 3 #include <string> 4 #include <string.h> 5 #include <stdlib.h> 6 #include <algorithm> 7 using namespace std; 8 #define MAXN 26 9 10 char word[50005][50]; 11 char ss1[50],ss2[50]; 12 int num; 13 14 struct TrIE{ 15 int Flag; 16 TrIE *Next[MAXN]; 17 TrIE() 18 { 19 Flag=0; 20 memset(Next,sizeof(Next)); 21 } 22 }*Root; 23 24 voID Insert(char *str) 25 { 26 TrIE *p=Root; 27 TrIE *q=NulL; 28 int len=strlen(str); 29 for(int i=0;i<len;i++) 30 { 31 int key=str[i]-‘a‘; 32 if(!p->Next[key]) 33 { 34 q=new TrIE(); 35 p->Next[key]=q; 36 } 37 p=p->Next[key]; 38 if(i==len-1) 39 p->Flag=1; 40 } 41 return; 42 } 43 44 int Qurey(char *str) 45 { 46 TrIE *p=Root; 47 int len=strlen(str); 48 int flag=0; 49 for(int i=0;i<len;i++) 50 { 51 int key=str[i]-‘a‘; 52 if(!p->Next[key]) 53 { 54 return 0; 55 } 56 p=p->Next[key]; 57 } 58 return p->Flag; 59 } 60 61 voID Find(char *str) 62 { 63 int len=strlen(str); 64 for(int m=1;m<len;m++) 65 { 66 //这里用strncmp 67 strncpy(ss1,str,m); 68 ss1[m]=0; 69 strncpy(ss2,str+m,len-m+1); 70 ss2[len-m+1]=0; 71 // 不用strncmp的话 72 // int j=0; 73 // for(int i=0;i<m;i++) 74 // { 75 // ss1[j++]=str[i]; 76 // } 77 // ss1[j]=0; 78 // j=0; 79 // for(int i=m;i<len;i++) 80 // { 81 // ss2[j++]=str[i]; 82 // } 83 // ss2[j]=0; 84 //printf("ss1=%s ss2=%s\n",ss1,ss2); 85 if(Qurey(ss1)&&Qurey(ss2)) 86 { 87 puts(str); 88 break; //不带break;就wa掉了，无语 89 } 90 } 91 } 92 93 voID Free(TrIE *T) 94 { 95 if(T==NulL) return; 96 for(int i=0;i<MAXN;i++) 97 { 98 if(T->Next[i]) Free(T->Next[i]); 99 }100 delete(T);101 }102 103 int main()104 {105 freopen("sampletem.txt","r",stdin);106 char str[50];107 Root=new TrIE();108 while(~scanf("%s",str))109 {110 strcpy(word[num++],str);111 Insert(str);112 }113 for(int i=0;i<num;i++)114 {115 Find(word[i]);116 }117 Free(Root);118 return 0;119 }
What Are You Talking About
HDU1075
Problem DescriptionIgnatius is so lucky that he met a Martian yesterday. But he dIDn‘t kNow the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?
input The problem has only one test case,the test case consists of two parts,the dictionary part and the book part. The dictionary part starts with a single line contains a string "START",this string should be ignored,then some lines follow,each line contains two strings,the first one is a word in English,the second one is the corresponding word in Martian‘s language. A line with a single string "END" indicates the end of the directory part,and this string should be ignored. The book part starts with a single line contains a string "START",then an article written in Martian‘s language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation,if you can‘t find the word in the dictionary you do not have to translate it,and just copy the old word to your translation. Space(‘ ‘),tab(‘\t‘),enter(‘\n‘) and all the punctuation should not be translated. A line with a single string "END" indicates the end of the book part,and that‘s also the end of the input. All the words are in the lowercase,and each word will contain at most 10 characters,and each line will contain at most 3000 characters. Output In this problem,you have to output the translation of the history book. Sample inputSTARTfrom fiwohello difhmars riwosfearth fnnvklike fiiwjENDSTARTdifh,i‘m fiwo riwosf.i fiiwj fnnvk!ENDSample Output
hello,i‘m from mars.i like earth!Hint
Huge input,scanf is recommended.
本题的题意是给你火星文与地球文的映射方式，然后给你一个火星文组成的文本，若某单词在映射文本中出现过，则输出映射之后的文本。否则输出原文本。
字典树，经典题，字典翻译。 WA了1次，后来发现是我把要翻译的单词搞错了，如果一个可以翻译的较长的单词包含着另一个可以翻译的较短的单词，这样遍历句子的时候就会先碰到较短的单词，WA的程序会先把这个短单词翻译出来，但实际上这是不对的，应该翻译整个较长的单词，而不是遇到什么就翻译什么。 我的程序运行时间是281MS，用链表做的，用数组应该会快些。 题意： 只有一组测试数据，分成两部分。 第一部分是字典，给你若干个单词以及对应的翻译，以START开始，END结束； 第二部分是翻译部分，给你若干句子，要求你根据上面给出的字典，将火星文翻译成英文，以START开始，END结束。这里翻译的时候，要 注意只有字典中有对应翻译的单词才翻译，字典中没有对应翻译的单词以及标点符号空格原样输出。 思路： 将字典中的火星文单词，也就是右边的单词构造成一棵字典树。在单词结束的节点中存储其对应的英文翻译。输入的时候读取整行，然后遍历每一个字符，将所有字母连续的记录到一个字符数组中，直到遇到一个非英文字母的字符为止，这个时候从字典树中查找这个单词有没有对应的英文翻译，如果有，输出这个翻译，如果没有，输出原来的单词。 注意： 1.输入方法，使用的scanf+gets。 2.不要搞错要翻译的单词，遇到一个非字母的字符算一个单词。 3.尽量不要使用cin，cout，容易超时1 #include <cstdio> 2 #include <iostream> 3 #include <string> 4 #include <string.h> 5 #include <stdlib.h> 6 #include <algorithm> 7 using namespace std; 8 #define MAXN 26 9 string fin=""; 10 11 struct TrIE{ 12 int Flag; 13 TrIE *Next[MAXN]; 14 string chc; 15 TrIE() 16 { 17 Flag=0; 18 memset(Next,sizeof(Next)); 19 } 20 }*Root; 21 22 voID Insert(string str,string ss) 23 { 24 TrIE *p=Root; 25 TrIE *q=NulL; 26 int len=str.size(); 27 for(int i=0;i<len;i++) 28 { 29 int key=str[i]-‘a‘; 30 if(!p->Next[key]) 31 { 32 q=new TrIE(); 33 p->Next[key]=q; 34 } 35 p=p->Next[key]; 36 if(i==len-1) 37 p->Flag=1; 38 p->chc=ss; 39 } 40 return; 41 } 42 43 voID Qurey(string str) 44 { 45 TrIE *p=Root; 46 int len=str.size(); 47 int flag=0; 48 for(int i=0;i<len;i++) 49 { 50 int key=str[i]-‘a‘; 51 if(!p->Next[key]) 52 { 53 flag=1; 54 break; 55 } 56 else 57 p=p->Next[key]; 58 if(i==len-1&&p->Flag==1) 59 fin+=p->chc; 60 } 61 if(flag||p->Flag!=1) 62 fin+=str; 63 return; 64 } 65 66 int main() 67 { 68 //freopen("sampletem.txt",stdin); 69 string a,b; 70 Root=new TrIE(); 71 cin>>a; 72 while(cin>>a) 73 { 74 if(a[0]==‘E‘) 75 break; 76 cin>>b; 77 Insert(b,a); 78 } 79 cin>>a; 80 getchar(); 81 char c; 82 string tem=""; 83 while(c=getchar()) 84 { 85 if(c==‘E‘) 86 { 87 c=getchar(); 88 c=getchar(); 89 break; 90 } 91 else if(c>=‘a‘&&c<=‘z‘) 92 { 93 tem+=c; 94 } 95 else 96 { 97 if(tem!="") 98 Qurey(tem); 99 fin+=c;100 tem="";101 }102 }103 cout<<fin;104 return 0;105 }总结
以上是内存溢出为你收集整理的Tire树(字典树)全部内容，希望文章能够帮你解决Tire树(字典树)所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）