题目链接：hdu1075
/*hdu 1075 What Are You Talking About(字典树)
题目大意：
每行输入两个单词，第二个单词可以翻译成第一个单词。
给出一串字符，能翻译的输出翻译后的单词，不能的原样输出。
思路：字典树
*/
#include
#include
#include
#include
#include
#include
using namespace std; bool flag; struct node { bool flag; char str[15]; node *next[26]; }*root; node *build()//建立结点 { node *p = (node *)malloc(sizeof(node)); for(int i = 0; i < 26; i ++) p -> next[i] = NULL; p -> flag = false; return p; } void save(char *a, char *s) { int len = strlen(s); node *p; p = root; for(int i = 0; i < len; i ++) { if(p -> next[s[i] - 'a'] == NULL) p -> next[s[i] - 'a'] = build(); p = p -> next[s[i] - 'a']; } p -> flag = true;//标记，单词的最后一个字符 strcpy(p -> str, a);//在该结点将翻译后的单词存下 } void query(char *s) { int len = strlen(s); node *p; p = root; for(int i = 0; i < len; i ++) { if(p -> next[s[i] - 'a'] == NULL) { printf("%s",s); return; } p = p -> next[s[i] - 'a']; } if(p -> flag)//单词能被翻译 printf("%s", p -> str); else printf("%s", s); } int main() { char s1[15],s2[15],ss[3005]; scanf("%s",s1); root = build(); while(scanf("%s",s1), strcmp(s1, "END")) { scanf("%s",s2); save(s1, s2); } scanf("%s",s1); getchar(); while(gets(ss), strcmp(ss, "END")) { int len = strlen(ss); for(int i = 0; i < len; i ++) { if(islower(ss[i])) { int j = 0; memset(s1, '\0', sizeof(s1)); while(islower(ss[i])) s1[j++] = ss[i++]; query(s1); } if(!islower(ss[i])) printf("%c",ss[i]); } if(islower(ss[len-1])) query(s1); printf("\n"); } return 0; }