HDU 1075 What Are You Talking About Trie题解

翻译火星语,不过火星语也是使用英文单词的,就是把一个单词对应到另外一个单词。

可以使用map, 使用二分,方法很多。

不过最快的应该都是Trie解法了。

把火星语挂在Trie树中,然后在叶子节点增加一个string容器,装英语单词。

查找的时候,找到了出现在Trie中的火星语,就返回string就可以了。

#include <stdio.h>
#include <string>
#include <string.h>
using namespace std;
const int MAX_N = 3001;
const int MAX_WORD = 11;
const int ARR_SIZE = 26;
char gEng[MAX_WORD], gMar[MAX_WORD];
char sentence[MAX_N];

struct Node
{
    string eng;
    Node *arr[ARR_SIZE];
    int n;
    Node():n(0), eng()
    {
        for (int i = 0; i < ARR_SIZE; i++)
        {
            arr[i] = NULL;
        }
    }
};

void delTrie(Node *trie)
{
    if (trie)
    {
        for (int i = 0; i < ARR_SIZE; i++)
        {
            if (trie->arr[i]) delete trie->arr[i], trie->arr[i] = NULL;
        }
        delete trie;
    }
}

Node *Trie;

void insertTrie(char eng[], char mar[])
{
    Node *pCrawl = Trie;
    int len = strlen(mar);
    for (int i = 0; i < len; i++)
    {
        int index = mar[i] - 'a';
        if (!pCrawl->arr[index]) pCrawl->arr[index] = new Node;
        pCrawl = pCrawl->arr[index];
    }
    pCrawl->eng = eng;
    pCrawl->n++;
}

string searchTrie(char mar[])
{
    Node *pCrawl = Trie;
    int len = strlen(mar);
    for (int i = 0; i < len; i++)
    {
        int index = mar[i] - 'a';
        if (!pCrawl->arr[index]) return string();
        pCrawl = pCrawl->arr[index];
    }
    return pCrawl->eng;
}

int main()
{
    Trie = new Node;
    scanf("%s", gEng);
    while (scanf("%s %s", gEng, gMar) && strcmp(gEng, "END"))
    {
        insertTrie(gEng, gMar);
    }
    getchar();    //get rid of '\n'

    while (gets(sentence) && strcmp(sentence, "END"))
    {
        int len = strlen(sentence);
        for (int i = 0; i < len; )
        {
            int j = 0;
            for (; i < len && 'a'<=sentence[i] && sentence[i]<='z'; i++)
            {
                gMar[j++] = sentence[i];
            }
            gMar[j] = '\0';//注意字符串后面的'\0'结束符号,否则答案错误

            string str = searchTrie(gMar);
            if (str.empty()) printf("%s", gMar);
            else printf("%s", str.c_str());

            if (i < len) putchar(sentence[i++]);
        }
        putchar('\n');
    }
    delTrie(Trie);
    return 0;
}

HDU 1075 What Are You Talking About Trie题解

时间: 08-01

HDU 1075 What Are You Talking About Trie题解的相关文章

HDU 1075 What Are You Talking About(Trie的应用)

What Are You Talking About Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 102400/204800 K (Java/Others) Total Submission(s): 20680    Accepted Submission(s): 6852 Problem Description Ignatius is so lucky that he met a Martian yesterday. But

HDU 1075 What Are You Talking About (map解法+Trie解法)

HDU 1075 What Are You Talking About (map解法+Trie解法) ACM 题目地址: HDU 1075 What Are You Talking About 题意: 给出一个"翻译-原文"的对应表,然后给出句子,要把句子中的原文都翻译出来. 分析: 可以用map赤裸裸地做,但是比较花费时间,虽然这题时间给了5s,map解法是能过的. 不过Trie解法500+ms,果然Trie字典树才是正解啊. Trie入门题. 另外发现ios_base::sync_

hdu 1075 字典树

// hdu 1075 字典树 // // 题目大意: // // 给你一个字典,即有两个字符串,一个是英文,一个是火星文,然后 // 输入一段火星文,要你翻译成英文. // // 解题思路: // // 字典树,查字典嘛,有就输出查到的,没有原样输出.将火星文插入到 // 字典树中,然后在字典输中查找.找到了,输出对应的英文,否则,原样输 // 出. // // 感悟: // // 题目确实很简单,但是,没告诉数据范围啊,导致我一直RE,原来单词 // 可能对应很长的英文啊,找人家ac的开数组

HDU 1251 统计难题 Trie题解

基本上是标准的寻找前缀的问题,只需要insert和search函数就可以了. 我这里主要是修改一下n的记录方法,这里的n代表的不是叶子节点的标志,而是有多少单词经过了这条路径的标志. 然后是查找需要查找的前缀单词,如果没有找到,就返回0,表示没有单词以这个前缀单词为前缀,如果找到,直接返回n就是答案了.因为有n个单词经过了这条路径. 查找效率是常数. 使用静态分配空间的办法. #include <stdio.h> #include <string.h> const int MAX_

HDU 11488 Hyper Prefix Sets (字符串-Trie树)

H Hyper Prefix Sets Prefix goodness of a set string is length of longest common prefix*number of strings in the set. For example the prefix goodness of the set {000,001,0011} is 6.You are given a set of binary strings. Find the maximum prefix goodnes

HDU 1247 Hat’s Words Trie题解

使用Trie的insert函数,主要是要灵活修改search函数,使得其可以快速搜索hat word. 思路: 1 先搜索一个word的前缀有没有在Trie树中找到,如果找到,保存这个Node,方便下面继续搜索, 就搜索余下的能不能是Trie树上的一个单词,如果找到,那么就是hat word了. 2 如果没找到,那么就沿着刚刚搜索到的前缀单词的节点继续往下搜,这样就可以加速程序,不用每次重复搜索. 3 如果沿着Trie树已经走到word的叶子节点了,那么就结束这个word的搜索了. 实现好这些思

HDU 1075 map or 字典树

What Are You Talking About Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 102400/204800 K (Java/Others)Total Submission(s): 12773    Accepted Submission(s): 4069 Problem Description Ignatius is so lucky that he met a Martian yesterday. But

HDU 4760 Good FireWall 完善Trie题解

本题乍看像是线段树之类的区间操作,不过因为只是需要查找ip的前缀,故此其实是使用Trie来做. 这里的Trie使用到了Delete函数,这是个Trie函数中最难的函数了,当然要使用数组记录的方法水掉,也是可以的.这里不水,给出delete函数. 考点难点: 1 Trie的操作函数的灵活运用,主要难点是delete函数的灵活运用 2  在叶子节点所有的group id, 删除的时候要注意,不能一气删除了,有多个group id会挂在同一颗树中 3  源ip和目的ip也许在多个叶子节点中,要使用两个

HDU 3065 病毒侵袭持续中 AC自动机题解

其实本题比HDU的病毒侵袭1还简单,不过有一个陷阱卡到我了:就是搜索text的时候,当遇到的字母不是大写字母的时候,那么就要重新从根节点开始搜索,否则就会答案错误. 那么一点陷阱,居然没想到啊. 教训啊:看来对不太平常的地方,需要更加深入的思考,才能发现其中的陷阱,否则就WA了. #include <stdio.h> #include <string.h> #include <queue> using std::queue; const int MAX_N = 1001