题目链接
1.题目描述
有一本字典，英语对应外语，现在要求输入一个外语单词，如果字典中相应的英语解释就输入对应的英语单词，否则输出ｅｎ； 1. 字典中的单词书 n < 2. 要求判别的单词没有给出（注意输入）
2.解题思路 ＞map容器 – map<string, bool> flag //表示一个外语单词是否对应英语单词 – map<string，string> mp //表示外语单词对应的英语单词
复杂度： 容器一般很耗时，，但具体时间还没不会算。（Memory: 17316KTime: 1563MS）
>Trie树
1. 建树，ch[][26+1] , 设一个单词的末尾节点在Trie树中的编号为N，那么ch[N][26] 就存贮这个单词对应的英语单词的下标。 2. mp[][11] 存贮的是英语单词 3. 输入字典时，假设读到了第 i 行，那么英语单词就放入了mp[ i ]中，同时插入了第 i 个外语单词，那么插入的时候到这么单词的末尾节点我们就存入了ch[N][26] = i ; 4. 查找的过程和插入的过程类似。每读入一个外语单词，我们就在Tries树中按顺序往下找，直到最后一个字母，取出ch[N][26]并返回；若查询的过程失败，即Tries树中没有这个单词，那么返回0。（这里的 i 显然从1开始）
复杂度： 一遍建树的过程（Memory: 13764KTime: 438MS）
3.代码
map容器：
;int main(){map<string, bool> flag;map<string, string> mp;char ch[11], fore[11];while(1){char t;if((t = getchar() )== ‘\n’) break;else{ch[0] = t;int n = 1;while(1){t = getchar();if(t == ‘ ‘){ch[n] = ‘\0’;break;}ch[n++] = t;}}cin>>fore;getchar();flag[fore] = true;mp[fore] = ch;}char wo[11];while(cin>>wo) //注意不要用scanf，小心超时和Output Limit Exceeded{if(flag[wo]) cout<<mp[wo]<<endl;else printf(“eh\n”);}return 0;}
Trie树：
;int ch[1000000+10][26+1];char mp[100000][11];int sz;void insert(char *s, int total){int n, u = 0;n = strlen(s);for(int i = 0; i<n; i++){int c = s[i] – ‘a’;if(ch[u][c] == -1){memset(ch[sz], -1, sizeof(ch[sz]));ch[u][c] = sz++;}u = ch[u][c];if(i == n-1) ch[u][26] = total;}return ;}int search(char *s){int n, u = 0;n = strlen(s);for(int i = 0; i<n; i++){int c = s[i] – ‘a’;if(ch[u][c] == -1) return 0;u = ch[u][c];if(i == n-1) return ch[u][26];}}int main(){sz = 1;memset(ch[0], -1, sizeof(ch[0]));char ch[11], fore[11];int total = 0;while(1){total++;char t;if((t = getchar() )== ‘\n’) break;else{ch[0] = t;int n = 1;while(1){t = getchar();if(t == ‘ ‘){ch[n] = ‘\0’;break;}ch[n++] = t;}}cin>>fore;getchar();insert(fore,total);strcpy(mp[total], ch);}char wo[11];while(cin>>wo) //注意不要用scanf，小心超时和Output Limit Exceeded{int ans = search(wo);if(ans) printf(“%s\n”,mp[ans]);else printf(“eh\n”);}return 0;}
就会犯错误，就会有无数次让自己跌倒的机会出现，
