首页 > 代码库 > ZOJ 1109 Language of FatMouse

ZOJ 1109 Language of FatMouse

主要是字符串查找,有多种解法:

 

算法一:Trie(时间效率最高)(27888KB)

#include <stdio.h>#include <stdlib.h>#include <string.h>const int CHAR_LEN = 11; /* 单词长度 */const int ALPH_LEN = 26; /* 字母个数 */const int MAX = 22; /* 一行字符串的最大长度 */const char EXIST = 1; /* 存在为‘1‘, ‘0‘反之 */const char NON_EXIST = 0;const int ZERO = 0;const char FIRST_CHAR = a;/* 字典树建立 */typedef struct node {    struct node *child[ALPH_LEN];    char trans[CHAR_LEN]; /* 翻译 */    char exist; /* 判断是否存在此FatMouse单词 */}node, *Node;Node root; /* 字典树根结点 *//* 插入FatMouse单词和相应的翻译 */void insert(char *fatM, char *trans){    int i, index, len;    Node current = NULL, newnode = NULL; /* 当前结点和新结点 */        len = strlen( fatM );    if (ZERO == len) /* 单词长度为0, 不需要插入 */    {        return;    }        current = root; /* 每次插入都要从根结点开始 */    for (i = 0; i < len; i++)    {        index = fatM[i] - FIRST_CHAR; /* 获取下标 */        if (NULL != current->child[index]) /* 当前字符存在字典树中 */        {            current = current->child[index];        }        else        {            if ((newnode=(Node) calloc (1, sizeof(node))) == NULL) {                printf("空间分配失败!\n");                exit( -1 );            }                        current->child[index] = newnode; /* 插入新结点 */            current = newnode; /* 修改当前结点位置 */        }    }        strcpy(current->trans, trans); /* 保存翻译 */    current->exist = EXIST; /* 此fatMouse单词存在 */}/* 翻译 */void translate(const char *fatM){    int i, index, len;    Node current = NULL; /* 当前结点 */        len = strlen( fatM );    if (ZERO == len) /* 此单词为空, 不需要翻译 */    {        return;    }        current = root; /* 每次都要从根结点开始搜 */    for (i = 0; i < len; i++)    {        index = fatM[i] - FIRST_CHAR; /* 获取下标 */        if (NULL != current->child[index]) /* 当前结点存在字典树中 */        {            current = current->child[index]; /* 修改当前位置 */        }        else        {            puts("eh");            return;        }    }        /* 判断并输出(匹配不一定存在字典树中) */    if (current->exist == EXIST) /* 此fatMouse单词存在字典树中 */    {        puts(current->trans);    }    else    {        puts("eh");    }}/* 释放内存 */void release(Node root){    int i;        for (i = 0; i < ALPH_LEN; i++)    {        if (NULL != root->child[i])        {            release( root->child[i] ); /* 释放孩子结点 */        }    }        free( root ); /* 释放 */    root = NULL; /* 指针置空 */}int main(){    char trans[CHAR_LEN], fatM[CHAR_LEN];    char tmp[MAX]; /* 接收一行 */    int i, len;        if ((root=(Node) calloc (1, sizeof(node))) == NULL) {        printf("空间分配失败!\n");        exit(-1);    }    while (gets(tmp), len = strlen(tmp))    {        for (i = 0; i < len; i++)        {            if (tmp[i] ==  )            {                break;            }        } /* 寻找分隔点 */                /* 找出两个单词 */        strcpy(fatM, tmp + i + 1);        tmp[i] = \0;        strcpy(trans, tmp);                insert(fatM, trans); /* 插入, 建立字典树 */    }        while (scanf("%s", fatM) != EOF)    {        translate( fatM );    }        return 0;}
牛人带注释版60ms
#include"iostream"using namespace std;#include"cstring"#include"cstdio"#include"malloc.h"struct trie{    trie *next[26];    bool flag;    char s[12];};trie *root;void insert(char *s,char *ans){    int id,l=strlen(s);    trie *p=root,*q;    for(int i=0;i<l;i++)    {        id=s[i]-a;        if(p->next[id]==NULL) {            q=(trie*)malloc(sizeof(trie));            q->flag=false;            for(int j=0;j<26;j++) q->next[j]=NULL;            p->next[id]=q;        }        p=p->next[id];    }    p->flag=true;    strcpy(p->s,ans);}bool can(trie *p){    for(int i=0;i<26;i++)        if(p->next[i]) return 1;    return 0;}void search(char *s){    int l=strlen(s);    trie *p=root,*q;    for(int i=0;i<l;i++)    {        q=p->next[s[i]-a];        if(q!=NULL) p=q;            else break;    }//    if(q!=NULL&&q->flag&&can(q))//    {//        while(can(q))//        for(int i=0;i<26;i++)//        if(q->next[i]) { putchar(‘a‘+i); q=q->next[i]; }//        puts("");//    }//        else puts("eh");    if(q!=NULL&&q->flag) puts(q->s);        else puts("eh");}int main(){    char s[30],key[30],ans[15];    root=(trie*)malloc(sizeof(trie));    for(int i=0;i<26;i++) root->next[i]=NULL;    while(gets(s))    {        if(!s[0]) break;        sscanf(s,"%s%s",ans,key);        insert(key,ans);    }    while(gets(s))    {        search(s);    }    return 0;}
我自己写的70ms

算法二:快排后二分查找()

#include"iostream"using namespace std;#include"algorithm"#include"cstdlib"#include"cstdio"#include"cstring"struct dic{    char key[11],ans[11];}d[100010];int cmp(const void *a,const void *b){    dic *x=(dic*)a;    dic *y=(dic*)b;    return strcmp((x->key),(y->key));}int main(){    char s[24];    int n=0;    while(gets(s))    {        if(!strlen(s)) break;        sscanf(s,"%s%s",d[n].ans,d[n].key);        ++n;    }    qsort(d,n,sizeof(d[0]),cmp);    dic *res=NULL;    while(gets(s))    {        res=(dic*)bsearch(s,d,n,sizeof(d[0]),cmp);        if(res!=NULL) puts(res->ans);            else puts("eh");    }    return 0;}
C版,100ms,4568KB
//sort效率笔qosrt高,貌似lower_bound()拖慢了很多#include"iostream"using namespace std;#include"algorithm"#include"vector"#include"cstdio"#include"cstdlib"#include"cstring"struct dic{    char key[12];    char ans[12];    bool operator<(const dic a) const    {        return strcmp(key,a.key)<0;    }//    bool operator==(const dic a) const//    {//        return strcmp(key,a.key)==0;//    }};dic v[100010];int main(){    //freopen("d:\\in.txt","r",stdin);    //freopen("d:\\out.txt","w",stdout);    dic c; int n=0;    char s[30];    while(gets(s))    {        if(!s[0]) break;        sscanf(s,"%s%s",v[n].ans,v[n].key);        n++;    }    sort(v,v+n);    //for(int i=0;i<n;i++) cout<<v[i].key<<‘ ‘<<v[i].ans<<endl;    while(gets(s))    {        strcpy(c.key,s);        dic *i=lower_bound(v,v+n,c);        //cout<<i-v<<endl;        if(i!=v+n&&strcmp(s,i->key)==0)            cout<<i->ans<<endl;        else cout<<"eh"<<endl;    }    return 0;}
C++版,940ms-1010ms,不稳定,人品不好会超时
#include"iostream"using namespace std;#include"algorithm"#include"vector"#include"cstdio"#include"cstdlib"#include"cstring"struct dic{    char key[12];    char ans[12];    bool operator<(const dic a) const    {        return strcmp(key,a.key)<0;    }};dic v[100010];//int l,r,m,cmp; bool ok;int main(){    //freopen("d:\\in.txt","r",stdin);    //freopen("d:\\out.txt","w",stdout);    int n=0;    char s[30];    while(gets(s))    {        if(!s[0]) break;        sscanf(s,"%s%s",v[n].ans,v[n].key);        n++;    }    sort(v,v+n);//    for(int i=0;i<n;i++) cout<<v[i].key<<‘ ‘<<v[i].ans<<endl;    while(gets(s))    {//        strcpy(c.key,s);//        dic *i=lower_bound(v,v+n,c);//        cout<<i-v<<endl;//        if(i!=v+n&&strcmp(s,i->key)==0)//            cout<<i->ans<<endl;//        else cout<<"eh"<<endl;//        l=ok=0; r=n-1;//        while(l<=r)//        {//            m=(l+r)>>1;//            cmp=strcmp(v[m].key,s);//            if(cmp==0) {ok=1; break;}//            else if(cmp>0) r=m-1;//            else l=m+1;//        }//        if(ok) puts(v[m].ans); else puts("eh");        int l=n-1,first=0,m,h;        while(l>0)        {            h=l>>1;            m=first+h;            if(strcmp(v[m].key,s)<0) { first=m+1; l=l-h-1; }                else l=h;        }        if(strcmp(v[first].key,s)==0) puts(v[first].ans); else puts("eh");    }    return 0;}
sort+自写二分,100ms

lower_bound也是二分查找啊,为何拖慢了这么多,找到源码自己写也是100ms,结构体比较sort正常,不知道lower_bound为什么这么慢!

c++的只用2616KB

算法三:Map映射(1300ms,15848KB)

"STL的map的查找时间复杂度在任何时候总是O(logN),因为map用的是红黑树,可以保证树的高度总是logN。"

#include"iostream"using namespace std;#include"map"#include"cstdio"#include"string"#include"algorithm"map<string,string> m;int main(){    //freopen("d:\\in.txt","r",stdin);    //freopen("d:\\out.txt","w",stdout);    string s;    while(getline(cin,s))    {        if(s.size()==0) break;        int pos = s.find( );        m[s.substr(pos+1)]=s.substr(0,pos);    }    while(cin>>s)    {        if(m.find(s)==m.end()) cout<<"eh"<<endl;        else cout<<m[s]<<endl;    }    return 0;}
View Code

算法四: 二叉查找树(190ms,12576KB)

#include <stdio.h>#include <stdlib.h>#include <memory>#include <string>#include <string.h>using namespace std;struct node {    char key[50],value[50];    struct node *left,*right;}*Head;void insert(const char *elem,const char *value,struct node * & p){    if( p == NULL)    {        p = (struct node*)malloc(sizeof(struct node));        strcpy(p->key,elem);        strcpy(p->value,value);        p->left = p->right = NULL;        return ;    }    if( strcmp(elem,p->key)>0 )        insert(elem,value,p->right);    else         insert(elem,value,p->left);}void find(const char *key,struct node *&p){    if(p==NULL)        printf("eh\n");    else if(strcmp(key,p->key)==0)        printf("%s\n",p->value);    else if(strcmp(key,p->key)>0)        find(key,p->right);    else        find(key,p->left);}int main(void){    char str[100],key[50],value[50];    while(gets(str) && strlen(str))    {        sscanf(str,"%s%s",value,key);        insert(key,value,Head);    }    while(scanf("%s",key)!=EOF)    {        find(key,Head);    }     Head=NULL;    return 0;}
排序二叉树

 

ZOJ 1109 Language of FatMouse