本文主要是介绍hdu 1075 字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
// hdu 1075 字典树
//
// 题目大意：
//
// 给你一个字典，即有两个字符串，一个是英文，一个是火星文，然后
// 输入一段火星文，要你翻译成英文。
//
// 解题思路：
//
// 字典树，查字典嘛，有就输出查到的，没有原样输出。将火星文插入到
// 字典树中，然后在字典输中查找。找到了，输出对应的英文，否则，原样输
// 出。
//
// 感悟：
//
// 题目确实很简单，但是，没告诉数据范围啊，导致我一直RE，原来单词
// 可能对应很长的英文啊，找人家ac的开数组的范围，AC了，这种题我真是无语
// 了，以我微薄的能力没看出什么能精确估计输入的规模啊，这道题真的有毒啊
// 没事，继续加油吧~~~FIGHTING!#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>using namespace std;
const int MAX_NODE = 1001200;
struct Trie{int ch[MAX_NODE][26];int val[MAX_NODE];int sz;void init(){sz = 1;memset(ch[0],0,sizeof(ch[0]));val[0] = 0;}int idx(char c){return c - 'a';}void insert(char *s,int v){int u = 0;int n = strlen(s);for (int i=0;i < n;i ++){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;}int query(char *s){int u = 0;int n = strlen(s);for (int i=0;i<n;i++){int c = idx(s[i]);if (!ch[u][c])return 0;u = ch[u][c];}return val[u];}
}trie;char str[30005];char id[MAX_NODE][15];
int cnt ;bool isapl(char c){if (c >= 'a' && c <= 'z')return true;return false;
}char p[4000];int main(){cnt = 1;//freopen("1.txt","r",stdin);trie.init();while(gets(str)){if (str[0]=='S') continue;if (str[0]=='E') break;int len = strlen(str);char s1[30005];int ind = 0;for (int i= 0;i < len;i++){if (!isapl(str[i])){id[cnt][i] = 0;ind = i+1;break;}id[cnt][i] = str[i];}int x;for (x=0;ind<len;x++,ind++){s1[x] = str[ind];}s1[x++] = 0;trie.insert(s1,cnt);cnt++;}while(gets(p)){if (p[0]=='S') continue;if (p[0]=='E') break;int len = strlen(p);char st[6000];int j = 0;for (int i=0;i<len;i++){//int j = i;if (isapl(p[i])){st[j++] = p[i];}else {st[j++] = 0;int no = 0;if (st[0]!=0){no = trie.query(st);if (no)printf("%s",id[no]);else{printf("%s",st);}}printf("%c",p[i]);//memset(st,0,sizeof(st));j=0;}}printf("\n");}return 0;
}
这篇关于hdu 1075 字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
