Blog·Tanky WooABOUTRSS

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

10 May 2011
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

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

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

字典树的讲解;

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

我用字典树做了一个:

// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1075
// Trie
#include 
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; inext[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; inext[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='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做的:

// 字典树
#include
#include
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='a' && tmp[i]<='z'))//非小写字母
            {
                tp[k]='\0';
                char *temp = find(tp);//查找是否有对应的engWord
                if(temp)//存在这个单词
                    printf("%s",temp);
                else                                                    
                    printf("%s",tp);//可以用cout<
#include
#include
using namespace std;
mapM;
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='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;
}