首页 > ACM题库 > HDU-杭电 > HDU 1075 What Are You Talking About-字典树-[解题报告] C++
2013
11-27

HDU 1075 What Are You Talking About-字典树-[解题报告] C++

What Are You Talking About

问题描述 :

Ignatius is so lucky that he met a Martian yesterday. But he didn’t know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?

输入:

The problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian’s language. A line with a single string "END" indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian’s language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can’t find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(‘ ‘), tab(‘\t’), enter(‘\n’) and all the punctuation should not be translated. A line with a single string "END" indicates the end of the book part, and that’s also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.

输出:

In this problem, you have to output the translation of the history book.

样例输入:

START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, i'm fiwo riwosf.
i fiiwj fnnvk!
END

样例输出:

hello, i'm from mars.
i like earth!

Hint
Huge input, scanf is recommended.

http://acm.hdu.edu.cn/showproblem.php?pid=1075 字典树

/*字典树,翻译*/
 #include<iostream>
 #include<cstring>
 #include<cstdlib>
 using namespace std;
 struct node
 {
    node* child[26];
    char word[12];
 };
 node*root=new node();
 void init()//初始化 
 {
    for(int i=0;i<26;i++) root->child[i]=NULL;
    strcpy(root->word,"");
 }
 void insert(char* s1,char* s2)//有s2 推s1 
 {
    int len=strlen(s2);
    node* cur=root;
    int i,pos,j;
    for(i=0;i<len;i++)
    {
       pos=s2[i]-'a';
       if(cur->child[pos]!=NULL) cur=cur->child[pos];
       else
       {
           cur->child[pos]=new node();
           node*temp=cur->child[pos];
           for(j=0;j<26;j++) temp->child[j]=NULL,strcpy(cur->word,"");//单词置空 
           cur=temp;
       }
    }
    strcpy(cur->word,s1);//s1放到对应的节点里面 
 }
 void print(char* s)//找出s对应的英语单词 
 {
    int len=strlen(s),i,j,pos;
    node*cur=root;
    for(i=0;i<len;i++)
    {
       pos=s[i]-'a';
       if(cur->child[pos]!=NULL) cur=cur->child[pos];
       else  break;
    }
    if(i==len && strlen(cur->word))  printf("%s",cur->word);//find
    else printf("%s",s);//not found , print itself
 } 
 int main()
 {
     
     init();
     char a[12],b[12],line[3008];
     scanf("%s",&a);//读取start 
     getchar();
     while(scanf("%s",&a)==1 && strcmp(a,"END"))//
     {
       scanf("%s",&b);
       insert(a,b);
     }
     scanf("%s",&a);//读取start
     getchar();//读回车 
     int i,len;
     string temp;
     while(gets(line) && strcmp(line,"END"))
     {
        //printf("line:%s\n",line);
        temp="";
        len=strlen(line);
        for(i=0;i<len;i++)
        {
           if(isalpha(line[i])) temp+=line[i];
           else 
           {
              //printf("temp:%s\n",&temp[0]);
               print(&temp[0]);//char* 
               temp="";
               printf("%c",line[i]);
           }
        }
        print(&temp[0]);
        strcpy(line,"");//
        
        print("\n");
        //printf("................................\n");
     }
     system("pause");
     return 0;
 }

 


  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮