首页 > 代码库 > HDU1075

HDU1075

题目大意:

给你一本火星词典,每个火星单词对应一个英文单词。

然后给你一篇火星文章,要求你翻译成英文。

要求如下:

如果这个火星单词用英文单词可以表示,就翻译成英文,如果没有这个单词,就原样输出。遇到标点符号或者空格原样输出即可。

____________________________________________________________________________________________

把给的每一个火星词建立trie,并在每个trie节点中建立一个字符串s,用来存储对应的英语单词,当然还要有exist存储是否构成单词。剩余的就是字符串的处理了!

____________________________________________________________________________________________

技术分享
 1 //hdu 1075
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 struct tn
 9 {
10     tn * next[26];
11     bool exist;
12     char s[12];
13 }*root;
14 tn * create()
15 {
16      tn * tp=new(tn);
17      tp->exist=0;
18      memset(tp->next,0,sizeof(tp->next));
19      tp->s[0]=\0;
20      return tp;
21 }
22 void insert(char *ss,char *s)
23 {
24     tn * p=root;
25     char *q=ss;
26     while(*q)
27     {
28         int id=*q-a;
29         if(p->next[id]==NULL)p->next[id]=create();
30         p=p->next[id];
31         q++;
32     }
33     p->exist=1;
34     strcpy(p->s,s);
35 }
36 char * search(char *ss)
37 {
38     tn *p=root;
39     char *q=ss;
40     while(*q)
41     {
42         int id=*q-a;
43         p=p->next[id];
44         q++;
45         if(p==NULL)return NULL;
46     }
47     if(p->exist)return p->s;
48     else return NULL;
49 }
50 char s[3003],ss[3003],sss[12];
51 int main()
52 {
53     root=create();
54     scanf("%s",s);
55     while(scanf("%s",s) && strcmp(s,"END")!=0)
56     {
57         scanf("%s",ss);
58         insert(ss,s);
59     }
60     while(gets(ss) && strcmp(ss,"START")!=0);
61     int js;
62     while(gets(ss) && strcmp(ss,"END")!=0)
63     {
64         js=0;
65         for(int i=0;ss[i]!=0;++i)
66             if(ss[i]>=a && ss[i]<=z)sss[js++]=ss[i];
67             else 
68             {
69                 sss[js]=\0;
70                 char *tmp=search(sss);
71                 if(tmp==NULL)printf("%s",sss);
72                 else printf("%s",tmp);                
73                 printf("%c", ss[i]);
74                 js=0;
75             }
76         printf("\n");
77     }
78     return 0;
79 }
View Code

 

HDU1075