By yusijia

Updated:

Contents
  1. 1. 题目：
  2. 2. 分析：

题目：

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

分析：

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

  • 不另外创映射表，将映射表和字典树结合起来，索引值直接改为要索引的字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
//解法一：建一个映射表和字典树(烧内存，容易超时，但思路简单，用索引值，静态分配)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

const int MAXN = 3010;
const int N = 26;


struct node{
    int index;
    struct node *next[26];
}root;

char word[MAXN][10];
struct node node[MAXN];//这样就不用动态分配了,一开始就开好，然后直接拿来用
int pos;

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

void insert_node(int index, char *str)
{
    int len = strlen(str), i;
    struct node *p = &root;
    for(i = 0; i < len; i++)
    {
        if(p->next[str[i] - 'a'] == NULL)
            p->next[str[i] - 'a'] = newNode();
        p = p->next[str[i] - 'a'];
    }
    p->index = index;//索引值
}

int search_node(char *str)
{
    int len = strlen(str);
    int i;
    struct node *p = &root;
    for(i = 0; i < len; i++)
    {
        if(p->next[str[i] - 'a'] == NULL)
            return -1;
        p = p->next[str[i] - 'a'];
    }
    return p->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_node(tmp);
        if(cnt == -1)
            printf("%s",tmp);
        else
            printf("%s", word[cnt]);
        printf("%c" , str[j]);  //每个单词后面有输入过空格,所以输出这个空格
        i = j + 1;//跳过这个空格继续
    }
    printf("\n");
}

int main()
{
    pos = 0;

    char str[MAXN];
    int index = 0;

    scanf("%s", str);
    getchar();
    while(scanf("%s", word[index]))
    {
        if(strcmp(word[index], "END") == 0)
            break;
        scanf("%s", str);
        getchar();
        insert_node(index++, str);
    }
    scanf("%s%*c" , str);//这样也可以吃回车
    while(cin.getline(str, MAXN))//吃掉了回车
    {
        if(strcmp(str, "END") == 0)
            break;
        solve(str);
    }
    return 0;
}



//解法二：不另外创映射表，将映射表和字典树结合起来，索引值直接改为要索引的字符串
//(节约内存，动态分配)

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <cstring>
#include <ctype.h>
using namespace std;

const int MAXN = 3005;//题目要求最多3000个单词
const int N = 26;


struct node{
    char *s;
    struct node *next[26];
}root;

void insert_node(char *a, char *str)
{
    int len = strlen(str), i;
    struct node *p = &root;
    for(i = 0; i < len; i++)
    {
        if(p->next[str[i] - 'a'] == NULL)
        {
            p->next[str[i] - 'a'] = new struct node;
            p->next[str[i] - 'a']->s = NULL;
            memset(p->next[str[i]-'a']->next,0,sizeof(struct node *)*26);
        }
        p = p->next[str[i] - 'a'];
    }
    p->s = new char [15];//题目要求每个单词最多10个字母
    //p->s = a;// 一开始错在这里，字符串之间赋值要用strcpy，或用string对象
    strcpy(p->s, a);
    //DEBUG
    /*if(p->s != NULL)
            printf("%s",p->s);*/
}

char* search_node(char *str)
{
    int len = strlen(str);
    int i = 0;
    struct node *p = &root;
    for(i = 0; i < len; i++)
    {
        if(p->next[str[i] - 'a'] == NULL)
        {
            return NULL;
        }
        p = p->next[str[i] - 'a'];
    }
    return p->s;//索引
}

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++];
        char *cnt = search_node(tmp);
        if(cnt == NULL)
            printf("%s",tmp);
        else
            printf("%s", cnt);
        printf("%c" , str[j]);  //每个单词后面有输入过空格,所以输出这个空格
        i = j + 1;//跳过这个空格继续
    }
    printf("\n");
}

int main()
{
    char str[MAXN];
    char a[MAXN];

    scanf("%s", str);
    getchar();
    while(scanf("%s", a))
    {
        if(strcmp(a, "END") == 0)
            break;
        scanf("%s", str);
        getchar();
        insert_node(a, str);
    }
    scanf("%s%*c" , str);//这样也可以吃回车
    while(cin.getline(str, MAXN))//吃掉了回车
    {
        if(strcmp(str, "END") == 0)
            break;
        solve(str);
    }
    return 0;
}//这里只有一种情况，所以中途不delete//如果是做软件记得用了new后要考虑delete
Contents
  1. 1. 题目：
  2. 2. 分析：