首页 > 代码库 > poj-2503

poj-2503

2024-07-15 17:13:01   211人阅读

嘻嘻，这个是自己的思想打的代码，独一无二，居然过了。首先构造字典树的节点，包括一个root，我把要保存的对应信息，如dog ogdoy中的dog保存在一个数组中，这个数组原本是一个单词结束标志，注意string的使用，我的代码内存快爆掉了，刚刚过的。

#include<cstdio>#include<iostream>#include<queue>#include<string>#include<cstring>#include<algorithm>using namespace std;char str[50];char str1[11];char str2[11];string temp;const int maxn = 1000100;struct trie{    int ch[maxn][26],sz,root;    string inf[maxn];    int newnode(){        inf[sz] = "eh";        memset(ch[sz],0,sizeof(ch[sz]));        return sz++;    }    void init(){        sz = 0;        root = newnode();    }void insert(char *str1,char* str2){    int length = strlen(str1);    int now = root;    for(int i = 0;i < length;i++){        int &temp = ch[now][str1[i] - ‘a‘];        if(!temp){            temp = newnode();        }        now = temp;    }    inf[now] = str2;}void query(char *str){    int len = strlen(str);    int now = root;    for(int i = 0;i < len;i++){        now = ch[now][str[i]-‘a‘];        int tmp = now;        if(!tmp)        {            temp = "eh";            return;        }       else       {           now = tmp;       }    }    temp = inf[now];}}tr;int main(){    tr.init();  while(gets(str)&&str[0]){        sscanf(str,"%s%s",str2,str1);        tr.insert(str1,str2);    }    while(scanf("%s",str) != EOF){        tr.query(str);       cout << temp << endl;    }    return 0;}

 


联系
我们