當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

字典树 ZOJ1109 HDU1251 PKU1204 HDU1075

發(fā)布時(shí)間：2023/12/2 编程问答 29 豆豆

生活随笔收集整理的這篇文章主要介紹了字典树 ZOJ1109 HDU1251 PKU1204 HDU1075 小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

又稱單詞查找樹，Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

假設(shè)有abc，abcd，abd, b, bcd，efg，hii這7個(gè)單詞，可構(gòu)建字典樹如下：

查找一個(gè)字符串時(shí)，我們只需從根結(jié)點(diǎn)按字符串中字符出現(xiàn)順序依次往下走。如果到最后字符串結(jié)束時(shí)，對應(yīng)的結(jié)點(diǎn)標(biāo)記為紅色，則該字符串存在;否則不存在。
插入時(shí)也只需從根結(jié)點(diǎn)往下遍歷，碰到已存在的字符結(jié)點(diǎn)就往下遍歷，否則，建立新結(jié)點(diǎn);最后標(biāo)記最后一個(gè)字符的結(jié)點(diǎn)為紅色即可。

性質(zhì)?

　　它有3個(gè)基本性質(zhì)：

????? 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。

??????從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對應(yīng)的字符串。

????? 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

基本操作?

??????其基本操作有:查找插入和刪除,當(dāng)然刪除操作比較少見.我在這里只是實(shí)現(xiàn)了對整個(gè)樹的刪除操作,至于單個(gè)word的刪除操作也很簡單.

搜索字典項(xiàng)目的方法為：?

　　(1) 從根結(jié)點(diǎn)開始一次搜索；

　　(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索；

　　(3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對應(yīng)的子樹進(jìn)行檢索。

　　(4) 迭代過程……

　　(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。

　　其他操作類似處理

以上內(nèi)容來自百度百科：。對應(yīng)練習(xí)：ZOJ1109? HDU1251

ZOJ1109 Language of FatMouse

map方法 1320MS 9556K

代碼 #include<iostream> #include<string> #include<map> #pragma warning (disable:4786) using namespace std; int main() {map<string,string> m;int len,i;char str[40],a[20],b[20];while(1){gets(str);len=strlen(str);if(len==0)break;for(i=0;str[i]!=' ';i++);strncpy(a,str,i);a[i]=0;strncpy(b,str+i+1,len-i-1);b[len-i-1]=0;m[b]=a;}map<string,string>::iterator it;while(scanf("%s",str)!=EOF){it=m.find(str);if(it!=m.end())cout<<(*it).second<<endl;elseputs("eh");}return 0; }

字典樹：140MS 14960K

代碼 #include<stdio.h> #include<stdlib.h> #include<string.h> #define N 100006 typedef struct node{char s[12];int h;struct node *next[26]; }*Tree,T; void init(Tree &root) {root=(Tree)malloc(sizeof(T));root->h=0;for(int i=0;i<26;i++)root->next[i]=NULL; }void insert(char path[],char s[],Tree root) {int len,i,j;len=strlen(path);for(i=0;i<len;i++){if(root->next[path[i]-'a']==NULL){Tree t=(Tree)malloc(sizeof(T));for(j=0;j<26;j++){t->next[j]=NULL;t->h=0;}root->next[path[i]-'a']=t;}root=root->next[path[i]-'a'];}root->h=1;strcpy(root->s,s); }void find(char s[],Tree root) {int len,i;len=strlen(s);for(i=0;i<len;i++){if(root->next[s[i]-'a']!=NULL)root=root->next[s[i]-'a'];elsebreak;}if(i==len && root->h==1)puts(root->s);elseputs("eh"); }int main() {Tree root;int len,i;char str[25],a[12],b[12];init(root);while(1){gets(str);len=strlen(str);if(len==0)break;for(i=0;str[i]!=' ';i++);strncpy(a,str,i);a[i]=0;strncpy(b,str+i+1,len-i-1);b[len-i-1]=0;insert(b,a,root);}while(scanf("%s",str)!=EOF)find(str,root);return 0; }

HDU1251 統(tǒng)計(jì)難題? 140MS 43736K

代碼 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node{int cnt;struct node *next[26]; }*Tree,T; Tree root; void insert(char *str) //建字典樹 {int i;Tree p,newnode;p=root;for(; *str;str++){if(p->next[*str-'a']!=NULL){p=p->next[*str-'a'];p->cnt++;}else{newnode=(Tree)malloc(sizeof(T));for(i=0;i<26;i++)newnode->next[i]=NULL;p->next[*str-'a']=newnode;p=p->next[*str-'a'];p->cnt=1;}} }int find(char *str) //查找 {Tree p;p=root;for(;*str;str++){if(p->next[*str-'a']!=NULL)p=p->next[*str-'a'];elsereturn 0;}return p->cnt; }int main() {int i;char str[20];root=(Tree)malloc(sizeof(T));for(i=0;i<26;i++)root->next[i]=NULL;root->cnt=0;while(gets(str)){if(strcmp(str,"")==0)break;insert(str);}while(gets(str))printf("%d\n",find(str));return 0; }

PKU1204 Word Puzzles

字典樹：1485MS 14320K（對給定的單詞建樹，對表進(jìn)行暴力search）

代碼 #include<stdio.h> #include<string.h> #include<stdlib.h> #define N 1002 typedef struct tree{int count;struct tree *next[26]; }*Tree,T; Tree root; int l,c,w; char map[N][N]; int result[N][3]; int dir[8][2]={{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}}; void insert(char *s,int con) {Tree p=root,q;for(int i=0;s[i];i++){if(p->next[s[i]-'A']==NULL){q=(Tree)malloc(sizeof(T));memset(q->next,0,sizeof(q->next));q->count=-1;p->next[s[i]-'A']=q;}p=p->next[s[i]-'A'];}p->count=con; } void search(int x,int y,int k) {int x1=x,y1=y;Tree p=root;while(x1>=0 && x1<l && y1>=0 && y1<c){int id=map[x1][y1]-'A';if(p->next[id]==NULL)break;elsep=p->next[id];if(p->count!=-1){result[p->count][0]=x;result[p->count][1]=y;result[p->count][2]=k+'A';}x1+=dir[k][0]; y1+=dir[k][1];} } void slove() {int i,j,k;for(i=0;i<l;i++)for(j=0;j<c;j++)for(k=0;k<8;k++)search(i,j,k);for(i=0;i<w;i++)printf("%d %d %c\n",result[i][0],result[i][1],result[i][2]); } int main() {int i;char word[N];scanf("%d%d%d",&l,&c,&w);getchar();root=(Tree)malloc(sizeof(T));memset(root->next,0,sizeof(root->next));for(i=0;i<l;i++)gets(map[i]);for(i=0;i<w;i++){gets(word);insert(word,i);}slove();return 0; }

據(jù)說這題還可以用AC自動機(jī)實(shí)現(xiàn)，不了解AC自動機(jī)，有待提高……

HDU1075 同ZOJ1109同一道理，字典樹基本應(yīng)用。

map方法 3375MS 42368K 752B

代碼 #include<iostream> #include<string> #include<map> using namespace std; int main() {map<string,string> M;string a,b;cin>>a;while(cin>>a,a!="END"){cin>>b;M[b]=a;}cin>>a;getchar();char tmp[3005];while(gets(tmp),strcmp(tmp,"END")){int len=strlen(tmp);tmp[len++]=' ';tmp[len]=0;b="";for(int i=0;i<len;i++){if(!islower(tmp[i])){if(M[b]!="")cout<<M[b];elsecout<<b;b="";if(i!=len-1)cout<<tmp[i];}elseb+=tmp[i];}cout<<endl;}return 0; }

字典樹：437MS 59796K 1274B（可以用做模板了吧）

代碼 #include<stdio.h> #include<string.h> #include<ctype.h> #include<stdlib.h> typedef struct node{node *next[26];int h;char word[12];node(){h=0;memset(next,0,sizeof(next));} }*Tree,T; Tree root=new node();void insert(char *eng,char *mar) {Tree p=root;while(*mar){int id=*mar-'a';if(p->next[id]==NULL)p->next[id]=new node();p=p->next[id];mar++;}p->h=1;strcpy(p->word,eng); } char *find(char *str) {Tree p=root;while(*str){int id=*str-'a';if(p->next[id]==NULL)break;p=p->next[id];str++;}if(*str==NULL && p->h==1)return p->word;elsereturn NULL; }int main() {int i,k,len;char a[12],b[12],tmp[3005],tp[3005];char *p;scanf("%s",a);while(scanf("%s",a) && strcmp(a,"END")!=0){scanf("%s",b);insert(a,b);}scanf("%s",a);getchar();k=0;while(gets(tmp),strcmp(tmp,"END")){len=strlen(tmp);tmp[len++]=' ';tmp[len]=0;for(i=0;i<len;i++){if(!islower(tmp[i])){tp[k]=0;k=0;p=find(tp);if(p)printf("%s",p);elseprintf("%s",tp);if(i!=len-1)putchar(tmp[i]);}elsetp[k++]=tmp[i];}puts("");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的字典树 ZOJ1109 HDU1251 PKU1204 HDU1075的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

字典