hdu1075What Are You Talking About（字典树）

题目链接：hdu1075

/*hdu 1075 What Are You Talking About(字典树)
题目大意：
    每行输入两个单词，第二个单词可以翻译成第一个单词。
给出一串字符，能翻译的输出翻译后的单词，不能的原样输出。

思路：字典树

*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdlib>
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;
}

hdu1075What Are You Talking About（字典树）

原文：http://blog.csdn.net/jzmzy/article/details/19396899