首页 > 代码库 > 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;}
#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;}
算法二:快排后二分查找()
#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;}
//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;}
#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;}
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;}
算法四: 二叉查找树(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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。