hdu 1075 What Are You Talking About

本文从WordPress迁移而来, 查看全部WordPress迁移文章

字典树 Trie

题意:给出一个字典,右边的单词是英文单词,左边的单词是火星文。查询时给出一串火星文字符,如果一段火星文能对应一个英文单词就输出那个英文单词,如果这个火星文没有英文单词对应就直接输出这个火星文。查询的单词只包括小写字母,一切非小写字母都不用查询,直接输出即可

注意:写了个Trie是对的,小地方错了几次。单词总数达到10^6,如果有静态方法来建Trie的话数组开大点。对于一句话查询,有空格,符号等等,做好一个处理工作,否则Trie的查找时对的,这些小问题要调很久

一开始写了个代码。后来写了个水水的类,再做多几题,再把Trie的类完善好。凡事都是这样的嘛

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 1000010
#define MAX 5000010
#define M 3010
#define INF 0x3f3f3f3f
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

char s1[N][20],s2[N][20];
int n,tot,num;
struct Trie{
char ch;
int next[30];
}a[MAX];

inline void init_trie(){
tot = 1; a[0].ch = '#';
cl(a[0].next , -1);
}

inline void init_node(int pos,char ch){
a[pos].ch = ch;
cl(a[pos].next , -1);
}

void insert(char *s ,int index){
int fa = 0,child;
for(int i = 0; s[i]; i++){
child = s[i] - 'a';
if(a[fa].next[child] == -1){
a[fa].next[child] = tot;
init_node(tot,s[i]);
tot++;
}
fa = a[fa].next[child];
}
a[fa].next[26] = index;
}

int query(char *s){
int fa = 0,child,i;
for(i = 0; s[i]; i++){
child = s[i] - 'a';
if(a[fa].next[child] == -1) break;
fa = a[fa].next[child];
}
if(s[i]) return -1;
return a[fa].next[26];
}

void solve(char *str){
char s[M];
int id,i = 0;
for(id = 0; str[id]; id++){
if(islower(str[id])){
s[i++] = str[id]; s[i] = '\0';
}
else{
if(i){
int res = query(s);
if(res == -1) printf("%s",s);
else printf("%s",s1[res]);
}
printf("%c",str[id]);
i = 0;
}
}
if(i){
int res = query(s);
if(res == -1) printf("%s",s);
else printf("%s",s1[res]);
}
puts("");
}

int main(){
//freopen("case.txt","r",stdin);
char temp[20];
char s[M];
while(scanf("%s",temp)!=EOF){
init_trie();
n = 0;
while(true){
scanf("%s",s1[n]);
if(!strcmp(s1[n],"END")) break;
scanf("%s",s2[n]);
insert(s2[n],n);
n++;
}
scanf("%s",temp); getchar();
while(true){
gets(s);
if(!strcmp(s,"END")) break;
solve(s);
}
}
return 0;
}

Trie类

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
#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX 5000010
#define N 1000010
#define M 3010
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))

class Trie{
public:
int tot;
int next[MAX][30];

inline void Init_Trie(){
cl(next[0],-1); tot = 1;
}

inline void Init_Node(int pos){
cl(next[pos],-1);
}

void Insert(char *str,int index){
int fa = 0,child;
for(int i = 0; str[i]; i++){
child = str[i] - 'a';
if(next[fa][child] == -1){
Init_Node(tot);
next[fa][child] = tot++;
}
fa = next[fa][child];
}
next[fa][26] = index;
}

int Find(char *str){
int fa = 0,child;
for(int i = 0; str[i]; i++){
int child = str[i] - 'a';
if(next[fa][child] == -1) return -1;
fa = next[fa][child];
}
return next[fa][26];
}
};

int n;
char word[N][20];
Trie T;

void solve(char *str){
char s[M];
int id,i = 0;
for(id = 0; true; id++){
if(islower(str[id])){
s[i++] = str[id]; s[i] = '\0';
}
else{
if(i){
int res = T.Find(s);
if(res == -1) printf("%s",s);
else printf("%s",word[res]);
}
if(str[id] == '\0') break;
printf("%c",str[id]); i = 0;
}
}
puts("");
}

int main(){
char str[M],_str[20];
while(scanf("%s",_str)!=EOF){
T.Init_Trie();
n = 0;
while(true){
scanf("%s",word[n]);
if(!strcmp(word[n],"END")) break;
scanf("%s",_str);
T.Insert(_str,n++);
}
scanf("%s",_str); getchar();
while(true){
gets(str);
if(!strcmp(str,"END")) break;
solve(str);
}
}
return 0;
}