题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1075

 

题目大意：

给你一串火星文，让你输出翻译后的版本

 

思路：

这题的思路其实挺简单。但是如何进行输入想了好久！

 

具体的还是看代码吧（代码上有注释）：

 

  1 #include <stdio.h>
  2 #include <string.h>
  3 #include <string>
  4 #include <iostream>
  5 #include <stdlib.h>
  6 
  7 using namespace std;
  8 const int MAX_NODE = 1000005;
  9 const int CHARSET = 26;
 10 
 11 
 12 int trie[MAX_NODE][CHARSET]={0};
 13 //int color[MAX_NODE]={0};
 14 int vis[MAX_NODE]={0};
 15 int k;
 16 char key_Value[MAX_NODE][11];
 17 char Input_str[10000][3005];
 18 int p = 0;
 19 
 20 void insert(char w[])
 21 {
 22     int len = strlen(w);
 23     p = 0;  // 根结点
 24     for (int i=0;i<len;i++)
 25     {
 26         int c = w[i] - 'a';
 27         if (!trie[p][c])
 28         {
 29             trie[p][c] = k;
 30             k++;
 31         }
 32         p = trie[p][c];
 33     }
 34     vis[p] = 1;
 35     //color[p] = 1;
 36 }
 37 
 38 
 39 int search(string s)
 40 {
 41     int len = s.length();
 42     p = 0;
 43     for (int i=0;i<len;i++)
 44     {
 45         int c = s[i]-'a';
 46         if (!trie[p][c])
 47             return 0;
 48         p = trie[p][c];
 49     }
 50     if (vis[p])
 51         return p;
 52     else
 53         return 0;
 54 }
 55 
 56 
 57 int main()
 58 {
 59 #ifndef ONLINE_JUDGE
 60     freopen("../in.txt", "r", stdin);
 61 #endif
 62     char str[5005];
 63     scanf("%s",str);
 64     getchar();
 65     k = 1;
 66     p = 0;
 67     memset(trie,0, sizeof(trie));
 68     memset(vis,0, sizeof(vis));
 69     while (true)
 70     {
 71         char str_first[11],str_second[11];
 72         scanf("%s",str_first);
 73         if (str_first[0] == 'E' && str_first[1] == 'N' && str_first[2] == 'D')
 74             break;
 75         scanf("%s",str_second);
 76         insert(str_second);
 77         strcpy(key_Value[p],str_first); //记录点p对应的字符串
 78     }
 79     scanf("%s",str);
 80     getchar();
 81     int input_cnt = 0;
 82     while (true)
 83     {
 84         gets(Input_str[input_cnt]);
 85         if (strcmp(Input_str[input_cnt],"END") == 0)
 86             break;
 87         input_cnt++;
 88     }
 89     for (int i=0;i<input_cnt;i++)
 90     {
 91         int pos = 0;
 92         int input_length = strlen(Input_str[i]);
 93         while (pos<input_length)
 94         {
 95             string string1;
 96             //记录符合要求的单词
 97             while ((Input_str[i][pos] <= 'z' && Input_str[i][pos] >= 'a') && pos < input_length ) {
 98                 string1 += Input_str[i][pos++];
 99             }
100             int key = search(string1);
101             //无法翻译的就直接输出
102             if (!key && string1.length())
103             {
104                 cout << string1;
105             }
106             else
107             {
108                 printf("%s",key_Value[key]);
109             }
110             //不符合要求的就直接输出
111             while (true) {
112                 if ((Input_str[i][pos] > 'z' || Input_str[i][pos] < 'a') && pos < input_length) {
113                     printf("%c",Input_str[i][pos++]);
114                 }
115                 else
116                     break;
117             }
118         }
119         printf("\n");
120     }
121     return 0;
122 }