首页 > 代码库 > HDU 1075 What Are You Talking About Trie题解
HDU 1075 What Are You Talking About Trie题解
翻译火星语,不过火星语也是使用英文单词的,就是把一个单词对应到另外一个单词。
可以使用map, 使用二分,方法很多。
不过最快的应该都是Trie解法了。
把火星语挂在Trie树中,然后在叶子节点增加一个string容器,装英语单词。
查找的时候,找到了出现在Trie中的火星语,就返回string就可以了。
#include <stdio.h> #include <string> #include <string.h> using namespace std; const int MAX_N = 3001; const int MAX_WORD = 11; const int ARR_SIZE = 26; char gEng[MAX_WORD], gMar[MAX_WORD]; char sentence[MAX_N]; struct Node { string eng; Node *arr[ARR_SIZE]; int n; Node():n(0), eng() { for (int i = 0; i < ARR_SIZE; i++) { arr[i] = NULL; } } }; void delTrie(Node *trie) { if (trie) { for (int i = 0; i < ARR_SIZE; i++) { if (trie->arr[i]) delete trie->arr[i], trie->arr[i] = NULL; } delete trie; } } Node *Trie; void insertTrie(char eng[], char mar[]) { Node *pCrawl = Trie; int len = strlen(mar); for (int i = 0; i < len; i++) { int index = mar[i] - 'a'; if (!pCrawl->arr[index]) pCrawl->arr[index] = new Node; pCrawl = pCrawl->arr[index]; } pCrawl->eng = eng; pCrawl->n++; } string searchTrie(char mar[]) { Node *pCrawl = Trie; int len = strlen(mar); for (int i = 0; i < len; i++) { int index = mar[i] - 'a'; if (!pCrawl->arr[index]) return string(); pCrawl = pCrawl->arr[index]; } return pCrawl->eng; } int main() { Trie = new Node; scanf("%s", gEng); while (scanf("%s %s", gEng, gMar) && strcmp(gEng, "END")) { insertTrie(gEng, gMar); } getchar(); //get rid of '\n' while (gets(sentence) && strcmp(sentence, "END")) { int len = strlen(sentence); for (int i = 0; i < len; ) { int j = 0; for (; i < len && 'a'<=sentence[i] && sentence[i]<='z'; i++) { gMar[j++] = sentence[i]; } gMar[j] = '\0';//注意字符串后面的'\0'结束符号,否则答案错误 string str = searchTrie(gMar); if (str.empty()) printf("%s", gMar); else printf("%s", str.c_str()); if (i < len) putchar(sentence[i++]); } putchar('\n'); } delTrie(Trie); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。