HDU/HDOJ 1075 What Are You Talking About(字典树|STL map)

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1075

这题用字典树Trie做很麻烦,用STL map要简单多了。

字典树的讲解;

http://www.wutianqi.com/?p=1359

我用字典树做了一个:

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
// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1075
// Trie
#include <iostream>
using namespace std;
 
typedef struct Trie{
    //int v;
    Trie *next[26];
	char english[20];
}Trie;
 
Trie root;
 
void createTrie(char *eng, char *mar)
{
    int len = strlen(mar);
    Trie *p = &root, *q;
    for(int i=0; i<len; ++i)
    {
        int id = mar[i]-'a';
        if(p->next[id] == NULL)
        {
            q = (Trie *)malloc(sizeof(root));
			for(int j=0; j<26; ++j)
                q->next[j] = NULL;
			strcpy(q->english, "");
 
            p->next[id] = q;
            p = p->next[id];
        }
        else
		{
            p = p->next[id];
        }
    }
	strcpy(p->english, eng);
}
 
char* findTrie(char *str)
{
    int len = strlen(str);
    Trie *p = &root;
	int i;
    for(i=0; i<len; ++i)
    {
        int id = str[i]-'a';
        p = p->next[id];
        if(p == NULL)
            break;
    }
	if(str[i] == 0 && strcmp(p->english, "")!=0)
		return p->english;
	return 0;
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    char s1[15], s2[15], laji[15];
    int i;
	scanf("%s", laji);   // "START"
    while(scanf("%s", s1) && strcmp(s1, "END")!=0)
	{
		scanf("%s", s2);
        createTrie(s1, s2);
	}
	scanf("%s", laji);  // "START"
	getchar();
	char str[1000];
    while(gets(str) && strcmp(str, "END")!=0)
    {
		int len = strlen(str);
		str[len] = ' ';
		str[++len] = 0;
		char ss[1000];
		int k = 0;
		for(i=0; i<len; ++i)
		{
			if(!(str[i]>='a' && str[i]<='z'))
			{
				ss[k] = 0;
				char *t = findTrie(ss);
				if(t)
					printf("%s", t);
				else
					printf("%s", ss);
				k = 0;
				if(i != len-1)
					printf("%c", str[i]);
			}
			else
			{
				ss[k++] = str[i];
			}
		}
		printf("\n");
    }
    return 0;
}

这个是网上一位朋友的代码,分别是用字典树和map做的:

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
// 字典树
#include<iostream>
#include<string>
using namespace std;
int i;
struct dictree
{
    dictree *child[26];
    char engWord[11];
    dictree()//初始化非常的有必要
    {
        for(i=0;i<26;i++)
            child[i] = NULL;
        engWord[0]='\0';
    }
};
dictree root;
void insert(char eng[],char mar[])//构建字典树
{
    dictree *now = &root;
    char *tmp = mar;
    while(*tmp)
    {
        if(now->child[*tmp-'a']==NULL)
            now->child[*tmp-'a'] = new dictree;
        now = now->child[*tmp-'a'];
        tmp++;
    }
    strcpy(now->engWord,eng);    
}
 
char *find(char ch[])//查找单词
{
    dictree *p = &root;
    int k=0;
    while(1)
    {
        if(ch[k]=='\0' || p->child[ch[k]-'a']==NULL)
            break;
        p = p->child[ch[k]-'a'];
        k++;
    }
    if(ch[k]=='\0' && strcmp(p->engWord,"")!=0)
        return p->engWord;
    return NULL;
}
 
int main()
{
    char a[11],b[11];
    scanf("%s",a);//"START"
    while(scanf("%s",a) && strcmp(a,"END")!=0 )
    {
        scanf("%s",b);
        insert(a,b);
    }
    scanf("%s",a);//"START"
    getchar();//吃回车
    char tmp[3002];
    while(1)
    {
        gets(tmp);//用这个比getline()强
        if(strcmp(tmp,"END") == 0 )
            break;
        int i,len,k=0;
        len = strlen(tmp);
        tmp[len]=' ';//多加一个' ',输出的时候注意
        tmp[++len]='\0';
        char tp[3002];
        for(i=0;i<len;i++)
        {
            if(!(tmp[i]>='a' && tmp[i]<='z'))//非小写字母
            {
                tp[k]='\0';
                char *temp = find(tp);//查找是否有对应的engWord
                if(temp)//存在这个单词
                    printf("%s",temp);
                else                                                    
                    printf("%s",tp);//可以用cout<<tp;//不可以用puts(tp);用puts有换行
                k=0;
                if(i!=len-1)//最后有一个' '是多余的
                    cout<<tmp[i];//输出非小写字母字符
            }
            else //小写字母
                tp[k++]=tmp[i];
        }
        cout<<endl;
    }
    return 0;
}
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
// STL map
#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,string>M;
int main()
{
    string a,b;
    cin>>a;//"START"
    while(cin>>a && a!="END")
    {
        cin>>b;
        M[b] = a;
    }
    cin>>a;//"START"
    getchar();//吃回车
    char tmp[3005];
    while(1)
    {
        gets(tmp);//用这个比getline()强
        if(strcmp(tmp,"END") == 0 )
            break;
        int i,len;
        len = strlen(tmp);
        b = "";
        for(i=0;i<len;i++)
        {
            if(!(tmp[i]>='a' && tmp[i]<='z'))//非小写字母
            {
                if(M[b]!="")//存在这个单词
                    cout<<M[b];
                else
                    cout<<b;
                b="";
                cout<<tmp[i];
            }
            else //小写字母
                b+=tmp[i];
        }
        cout<<endl;
    }
    return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1075 What Are You Talking About(字典树|STL map)》有100个想法

  1. 很久没来了,刚好学到字典树,过来刷题~我也贴个代码,打个酱油~~
    // 250 MS
    #include
    #include
    #include
    using namespace std;

    struct Data {
    bool mark; // 标记当前节点是否有单词
    char work[15]; // 存储当前节点的单词
    Data *next[26];
    }*root;
    char str[3010];

    Data* Creat() {
    Data *p = new Data;
    for(int i = 0; i next[i] = NULL;
    //memset(p->work, 0, sizeof(p->work));
    p->mark = 0;
    return p;
    }

    void Insert(char *s1, char *s2) {
    Data *p = root;
    int len = strlen(s2);
    for(int i = 0; i next[u] == NULL)
    p->next[u] = Creat();
    p = p->next[u];
    }
    p->mark = 1;
    strcpy(p->work, s1);
    }

    void Translation(int s, int e) {
    Data *p = root;
    bool flag = 0;
    for(int i = s; i next[u] == NULL) {
    flag = 1; break;
    }
    p = p->next[u];
    }
    if(!flag && p->mark)
    // 火星文匹配完毕,且当前节点有英文单词
    printf(“%s”, p->work);
    else
    for(int i = s; i <= e; ++i) printf("%c", str[i]);
    }

    int main() {
    root = Creat();
    char s1[20], s2[20];
    scanf("%s", s1);
    while(scanf("%s", s1)!=EOF) {
    if(s1[0] == 'E') break;
    scanf("%s", s2);
    Insert(s1, s2); // 将单词插入字典
    }
    scanf("%s", s1);
    getchar(); // 注意gets()之前需要吸收回车符
    while(gets(str)) {
    if(strcmp(str, "END") == 0) break;
    int len = strlen(str);
    int s = 0, e = -1;
    // 记录当前单词的起点、终点
    for(int i = 0; i < len; ++i) {
    if('a' <= str[i] && str[i] <= 'z')
    e = i;
    else {
    if(s <= e) Translation(s, e);
    s = i+1, e = -1;
    printf("%c", str[i]);
    }
    }
    printf("\n");
    }
    return 0;
    }

发表评论

电子邮件地址不会被公开。 必填项已用*标注