hdu 1075 What Are You Talking About

点击打开hdu1075

题意：给定一个映射表的关系，给定每个单词的对应的映射的单词。现在给定一段字符串，要求如果单词能够翻译就进行翻译，否则原样输出，但是注意所有的\n，\r，空格以及所有的标点符号都是不翻译的。

思路：先对映射表的单词建立字典树，每个单词的尾节点标记这个单词所映射的单词的下标，那么对于给定的字符串，我们只要把所有的单词进行解析去字典树中查找即可。

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 30010;
const int N = 26;

struct Node{
   int index;
   Node* child[N];
};
char word[MAXN][10];
Node node[MAXN];
Node* root;
int pos;

Node* newNode(){
    node[pos].index = -1;
    for(int i = 0 ; i < N ; i++)
        node[pos].child[i] = NULL;
    return &node[pos++];
}

void insert(int index , char *str){
    Node* s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
        int num = str[i]-'a';
        if(s->child[num] == NULL)
            s->child[num] = newNode();
        s = s->child[num];
    }
    s->index = index;
}

int search(char *str){
    Node* s = root;
    int len = strlen(str);
    for(int i = 0 ; i < len ; i++){
        int num = str[i]-'a';
        if(s->child[num] == NULL)
            return -1;
        s = s->child[num];
    }
    return s->index;
}

void solve(char *str){
    int len = strlen(str);
    char tmp[MAXN];
    int i = 0;
    while(i < len){
        if(!islower(str[i])){
            printf("%c" , str[i]);
            i++;
            continue;
        }
        memset(tmp , '\0' , sizeof(tmp));
        int j = i;
        int index = 0;
        while(j < len && islower(str[j]))
           tmp[index++] = str[j++];
        int cnt = search(tmp);
        if(cnt == -1)
            printf("%s" , tmp);
        else
            printf("%s" , word[cnt]);
        printf("%c" , str[j]);
        i = j+1;
    }
    puts("");
}

int main(){
    pos = 0;
    root = newNode();
    char str[MAXN];
    int index = 0;

    scanf("%s" , str);
    while(scanf("%s" , word[index])){
        if(strcmp(word[index] , "END") == 0)
            break;
        scanf("%s" , str);
        insert(index++ , str);
    }
    scanf("%s%*c" , str);
    while(gets(str)){
        if(strcmp(str , "END") == 0)
            break;
        solve(str);
    }
    return 0;
}