碼迷,mamicode.com
首頁 > 其他好文 > 詳細

Tire樹(字典樹)

時間:2019-07-10 09:15:01      閱讀:266      評論:0      收藏:0      [點我收藏+]

標簽:sms   can   space   join   ext   空間換時間   拆分   guarantee   sdn极速时时彩走势图   

from:https://www.cnblogs.com/justinh/p/7716421.html

 Trie,又經常叫前綴樹,字典樹等等。它有很多變種,如后綴樹,Radix Tree/Trie,PATRICIA tree,以及bitwise版本的crit-bit tree。當然很多名字的意義其實有交叉。

 

定義

在計算機科學中,trie,又稱前綴樹或字典樹,是一種有序樹,用于保存關聯數組,其中的鍵通常是字符串。與二叉查找樹不同,鍵不是直接保存在節點中,而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴,也就是這個節點對應的字符串,而根節點對應空字符串。一般情況下,不是所有的節點都有對應的值,只有葉子節點和部分內部節點所對應的鍵才有相關的值。

trie中的鍵通常是字符串,但也可以是其它的結構。trie的算法可以很容易地修改為處理其它結構的有序序列,比如一串數字或者形狀的排列。比如,bitwise trie中的鍵是一串位元,可以用于表示整數或者內存地址

 

基本性質

极速时时彩走势图1,根節點不包含字符,除根節點意外每個節點只包含一個字符。

极速时时彩走势图2,從根節點到某一個節點,路徑上經過的字符連接起來,為該節點對應的字符串。

3,每個節點的所有子節點包含的字符串不相同。

 

優點

可以最大限度地減少無謂的字符串比較,故可以用于詞頻統計和大量字符串排序。

  跟哈希表比較:

    1,最壞情況時間復雜度比hash表好

    2,沒有沖突,除非一個key對應多個值(除key外的其他信息)

    3,自帶排序功能(類似Radix Sort),先序遍歷trie可以得到排序。

缺點

1,雖然不同單詞共享前綴,但其實trie是一個以空間換時間的算法。其每一個字符都可能包含至多字符集大小數目的指針(不包含衛星數據)。

每個結點的子樹的根節點的組織方式有幾種。1>如果默認包含所有字符集,則查找速度快但浪費空間(特別是靠近樹底部葉子)。2>如果用鏈接法(如左兒子右兄弟),則節省空間但查找需順序(部分)遍歷鏈表。3>alphabet reduction: 減少字符寬度以減少字母集個數。,4>對字符集使用bitmap,再配合鏈接法。

极速时时彩走势图2,如果數據存儲在外部存儲器等較慢位置,Trie會較hash速度慢(hash訪問O(1)次外存,Trie訪問O(樹高))。

极速时时彩走势图3,長的浮點數等會讓鏈變得很長。可用bitwise trie改進。

 

bit-wise Trie

類似于普通的Trie,但是字符集為一個bit位,所以孩子也只有兩個。

极速时时彩走势图可用于地址分配,路由管理等。

雖然是按bit位存儲和判斷,但因為cache-local和可高度并行,所以性能很高。跟紅黑樹比,紅黑樹雖然紙面性能更高,但是因為cache不友好和串行運行多,瓶頸在存儲訪問延遲而不是CPU速度。

 

壓縮Trie

壓縮分支條件:

极速时时彩走势图1,Trie基本不變

极速时时彩走势图2,只是查詢

3,key跟結點的特定數據無關

4,分支很稀疏

若允許添加和刪除,就可能需要分裂和合并結點。此時可能需要對壓縮率和更新(裂,并)頻率進行折中。

 

外存Trie

某些變種如后綴樹適合存儲在外部,另外還有B-trie等。

 

應用場景

(1) 字符串檢索
事先將已知的一些字符串(字典)的有關信息保存到trie樹里,查找另外一些未知字符串是否出現過或者出現頻率。
舉例:
1,給出N 個單詞組成的熟詞表,以及一篇全用小寫英文書寫的文章,請你按最早出現的順序寫出所有不在熟詞表中的生詞。
极速时时彩走势图2,給出一個詞典,其中的單詞為不良單詞。單詞均為小寫字母。再給出一段文本,文本的每一行也由小寫字母構成。判斷文本中是否含有任何不良單詞。例如,若rob是不良單詞,那么文本problem含有不良單詞。

3,1000萬字符串,其中有些是重復的,需要把重復的全部去掉,保留沒有重復的字符串。

 

(2)文本預測、自動完成,see also,拼寫檢查

 

(3)詞頻統計

1,有一個1G大小的一個文件,里面每一行是一個詞,詞的大小不超過16字節,內存限制大小是1M。返回頻數最高的100個詞。

2,一個文本文件,大約有一萬行,每行一個詞,要求統計出其中最頻繁出現的前10個詞,請給出思想,給出時間復雜度分析。

3,尋找熱門查詢:搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來,每個查詢串的長度為1-255字節。假設目前有一千萬個記錄,這些查詢串的重復度比較高,雖然總數是1千萬,但是如果去除重復,不超過3百萬個。一個查詢串的重復度越高,說明查詢它的用戶越多,也就越熱門。請你統計最熱門的10個查詢串,要求使用的內存不能超過1G。
(1) 請描述你解決這個問題的思路;
极速时时彩走势图(2) 請給出主要的處理流程,算法,以及算法的復雜度。

极速时时彩走势图==》若無內存限制:Trie + “k-大/小根堆”(k為要找到的數目)。

否則,先hash分段再對每一個段用hash(另一個hash函數)統計詞頻,再要么利用歸并排序的某些特性(如partial_sort),要么利用某使用外存的方法。參考

  “” 。

  “” 

    

 

(4)排序

Trie樹是一棵多叉樹,只要先序遍歷整棵樹,輸出相應的字符串便是按字典序排序的結果。
比如給你N 個互不相同的僅由一個單詞構成的英文名,讓你將它們按字典序從小到大排序輸出。

 

(5)字符串最長公共前綴
Trie樹利用多個字符串的公共前綴來節省存儲空間,當我們把大量字符串存儲到一棵trie樹上時,我們可以快速得到某些字符串的公共前綴。
舉例:
給出N 個小寫英文字母串,以及Q 個詢問,即詢問某兩個串的最長公共前綴的長度是多少?
解決方案:首先對所有的串建立其對應的字母樹。此時發現,對于兩個串的最長公共前綴的長度即它們所在結點的公共祖先個數,于是,問題就轉化為了離線(Offline)的最近公共祖先(Least Common Ancestor,簡稱LCA)問題。
而最近公共祖先問題同樣是一個經典問題,可以用下面幾種方法:
1. 利用并查集(Disjoint Set),可以采用采用經典的Tarjan 算法;
极速时时彩走势图2. 求出字母樹的歐拉序列(Euler Sequence )后,就可以轉為經典的最小值查詢(Range Minimum Query,簡稱RMQ)問題了;

 

(6)字符串搜索的前綴匹配
trie樹常用于搜索提示。如當輸入一個網址,可以自動搜索出可能的選擇。當沒有完全匹配的搜索結果,可以返回前綴最相似的可能。
Trie樹檢索的時間復雜度可以做到n,n是要檢索單詞的長度,
如果使用暴力檢索,需要指數級O(n2)的時間復雜度。

 

(7) 作為其他數據結構和算法的輔助結構
极速时时彩走势图如后綴樹,AC自動機等

后綴樹可以用于全文搜索

 

轉一篇關于幾種Trie速度比較的文章:

Trie樹和其它數據結構的比較 

 

參考:

[1] 維基百科:Trie, 

[2] LeetCode字典樹(Trie)總結, 

[3] 字典樹(Trie樹)的實現及應用, 

[4] 6天通吃樹結構—— 第五天 Trie樹, 

 

极速时时彩走势图在Trie樹中主要有3個操作,插入、查找和刪除。一般情況下Trie樹中很少存在刪除單獨某個結點的情況,因此只考慮刪除整棵樹。

 

 

例題及思路

統計難題

Problem Description

Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴). 

Input

輸入數據的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串. 

注意:本題只有一組測試數據,處理到文件結束. 

Output

對于每個提問,給出以該字符串為前綴的單詞的數量. 

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc

Sample Output

2
3
1
0

 

統計出以某個字符串為前綴的單詞數量,首先構建出trie樹并記錄每個節點的訪問次數,然后在上面查詢就好了,模板題。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <algorithm>
 5 #define MAXN 26
 6 using namespace std;
 7 
 8 struct Trie 
 9 {
10     Trie *Next[MAXN];
11     int Flag;
12     Trie()
13     {
14         Flag=1;
15         memset(Next,NULL,sizeof(Next));
16     }
17 };
18 
19 struct Trie* Root;
20 
21 void Insert(char* str)
22 {
23     Trie *p,*q;
24     p=Root;
25     int len=strlen(str);
26     for(int i=0;i<len;++i)
27     {
28         int key=str[i]-a;
29         if(p->Next[key]==NULL)
30         {
31             q=new Trie();
32             p->Next[key]=q;
33             p=p->Next[key];
34         }
35         else 
36         {
37             p=p->Next[key];
38             ++p->Flag;
39         }
40     }
41 }
42 
43 int Qurey(char *str)
44 {
45     int len=strlen(str);
46     Trie* p=Root;
47     for(int i=0;i<len;++i)
48     {
49         int key=str[i]-a;
50         if(p->Next[key]==NULL)
51             return 0;
52         p=p->Next[key];
53     }
54     return p->Flag;
55     
56 }
57 
58 void Free(Trie* T)
59 {
60     if(T==NULL) return;
61     for(int i=0;i<MAXN;i++)
62     {
63         if(T->Next[i]) Free(T->Next[i]);
64     }
65     delete(T);
66 }
67 
68 int main()
69 {
70     //freopen("sample.txt","r",stdin);
71     char str[15];
72     Root=new Trie();
73     while(*gets(str))   //效果等同于while(gets(str)&&str[0]!=0)
74     {
75         Insert(str);
76     }
77     while(~scanf("%s",str))
78     {
79         printf("%d\n",Qurey(str));
80     }
81     Free(Root);
82     return 0;
83 }

 

 

 

單詞數

Problem Description

lily的好朋友xiaoou333最近很空,他想了一件沒有什么意義的事情,就是統計一篇文章里不同單詞的總數。下面你的任務是幫助xiaoou333解決這個問題。

Input

有多組數據,每組一行,每組就是一篇小文章。每篇小文章都是由小寫字母和空格組成,沒有標點符號,遇到#時表示輸入結束。

Output

每組只輸出一個整數,其單獨成行,該整數代表一篇文章里不同單詞的總數。

Sample Input

you are my friend
#

Sample Output

 4

 

統計出現的不同單詞的個數,直接把字符全部插入Trie樹中,然后遍歷trie樹,統計所有具有End標記的節點個數就好了。

提示:多樣例輸入的格式是第一種,用字符數組會被卡

           技術圖片

這里可以用 istringstream來快速從字符串中根據空格來提取單詞,istringstream對象可以綁定一行字符串,然后以空格為分隔符把該行分隔開來。(要加頭文件sstream)

 

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <sstream> 
 6 #define MAXN 26
 7 using namespace std;
 8 
 9 struct Trie
10 {
11     Trie *Next[MAXN];
12     int flag;
13     int end;
14     Trie()
15     {
16         flag=1;
17         end=0;
18         memset(Next,NULL,sizeof(Next));
19     }
20 }*Root;
21 
22 void Insert(string str)
23 {
24     Trie *p=Root;
25     Trie *q;
26     int len=str.size();
27     for(int i=0;i<len;++i)
28     {
29         int key=str[i]-a;
30         if(p->Next[key]==NULL)
31         {
32             q=new Trie();
33             p->Next[key]=q;
34             p=p->Next[key];
35         }
36         else 
37         {
38             p=p->Next[key];
39             ++p->flag;
40         }
41         if(i==len-1)
42             p->end=1;
43     }
44 }
45 
46 int visit(Trie* T,int &sum) //遍歷trie樹
47 {
48     if(T==NULL)
49         return 0;
50     if(T->end==1)
51         sum++;
52     for(int i=0;i<MAXN;i++)
53     {
54         visit(T->Next[i],sum);
55     }
56 }
57 
58 void Free(Trie* T)
59 {
60     if(T==NULL) return;
61     for(int i=0;i<MAXN;i++)
62     {
63         if(T->Next[i]) Free(T->Next[i]);
64     }
65     delete(T);
66 }
67 
68 int main()
69 {
70     string str;
71     string tem;  //字符數組被卡,改用string就過了。。。。
72     int sum=0;
73     Root=new Trie();
74     while(getline(cin,str)&&str!="#")
75     {
76         istringstream is(str); //is相當于存單詞的一個容器
77         while(is>>tem)        //將is中的字符串依次賦給string
78         {
79             Insert(tem);
80         }
81         visit(Root,sum);
82         printf("%d\n",sum);
83         Free(Root);
84         Root=new Trie();
85         sum=0;
86     }
87     Free(Root);
88     return 0;
89 }

 

Shortest Prefixes

Description

A prefix of a string is a substring starting at the beginning of the given string. The prefixes of "carbon" are: "c", "ca", "car", "carb", "carbo", and "carbon". Note that the empty string is not considered a prefix in this problem, but every non-empty string is considered to be a prefix of itself. In everyday language, we tend to abbreviate words by prefixes. For example, "carbohydrate" is commonly abbreviated by "carb". In this problem, given a set of words, you will find for each word the shortest prefix that uniquely identifies the word it represents. 

In the sample input below, "carbohydrate" can be abbreviated to "carboh", but it cannot be abbreviated to "carbo" (or anything shorter) because there are other words in the list that begin with "carbo". 

An exact match will override a prefix match. For example, the prefix "car" matches the given word "car" exactly. Therefore, it is understood without ambiguity that "car" is an abbreviation for "car" , not for "carriage" or any of the other words in the list that begins with "car". 

Input

The input contains at least two, but no more than 1000 lines. Each line contains one word consisting of 1 to 20 lower case letters.

Output

The output contains the same number of lines as the input. Each line of the output contains the word from the corresponding line of the input, followed by one blank space, and the shortest prefix that uniquely (without ambiguity) identifies this word.

Sample Input

carbohydrate
cart
carburetor
caramel
caribou
carbonic
cartilage
carbon
carriage
carton
car
carbonate

Sample Output

carbohydrate carboh
cart cart
carburetor carbu
caramel cara
caribou cari
carbonic carboni
cartilage carti
carbon carbon
carriage carr
carton carto
car car
carbonate carbona

求一個能代表這個字符串的最短前綴,也就是只有這個字符串具有的前綴,否則輸出這個字符串本身

做法很顯然,先構建好Trie樹,然后對每個單詞進行find,遞歸到直到節點出現次數為1,表示這個節點只有這一個單詞走過,返回就ok。

這里可以用string不斷拼接字符,然后直接返回,減少一些代碼量。

 技術圖片

技術圖片

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 #define MAXN 26
 7 const int maxn=2e6+5;
 8 int Trie[maxn][MAXN];
 9 int Count[maxn];
10 bool End[maxn];
11 int tot;
12 
13 void Find(char *str)
14 {
15     int len=strlen(str);
16     int Root=0;
17     int flag=1;
18     int i;
19     for(i=0;i<len;i++)
20     {
21         int key=str[i]-a;
22         Root=Trie[Root][key];
23         printf("%c",str[i]);
24         if(Count[Root]==1)
25         {
26             printf("\n");
27             return;
28         }     
29     }
30     printf("\n");
31     return ;
32 }
33 
34 void Insert(char *str)
35 {
36     int len=strlen(str);
37     int Root=0;
38     for(int i=0;i<len;i++)
39     {
40         int key=str[i]-a;
41         if(!Trie[Root][key])
42         {
43             Trie[Root][key]=++tot;
44             Count[Trie[Root][key]]=1;
45         }
46         else
47         {
48             Count[Trie[Root][key]]++;
49         }    
50         Root=Trie[Root][key];
51     }
52     End[Root]=true;
53 }
54 
55 void init()
56 {
57     for(int i=0;i<tot;i++)
58     {
59         End[i]=false;
60         Count[i]=0;
61         for(int j=0;j<MAXN;j++)
62         {
63             Trie[i][j]=0;
64         }
65     }
66     tot=0;
67 }
68 char ss[1005][21];
69 int main()
70 {
71     int num=0;
72     while(scanf("%s",ss[num])!=EOF)
73     {
74         Insert(ss[num++]);
75     }
76     for(int i=0;i<num;i++)
77     {
78         printf("%s ",ss[i]);
79         Find(ss[i]);
80     }
81     init();
82     return 0;
83 }

 

 

Phone List

Description

极速时时彩走势图Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let‘s say the phone catalogue listed these numbers:

  • Emergency 911
  • Alice 97 625 999
  • Bob 91 12 54 26

In this case, it‘s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob‘s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n极速时时彩走势图 lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

极速时时彩走势图For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

給出一個字符串集合,問是否所有的字符串都不是其他字符串的前綴

如果字符串Xn=X1X2....Xn是字符串Ym=Y1Y2....Ym的前綴,有在插入的時候有兩種情況:Xn在Yn之前插入,Xn在Yn之后插入。
  1)如果Xn在Yn之前插入,那么在插入Yn的時候必然經過Xn的路徑,此時可以根據判斷在這條路徑上是否已經有結點被標記已經構成完成的字符串序列來判斷是否存在Yn的前綴;
  2)如果Xn在Yn之后插入,那么插入完成之后當前指針指向的結點的next數組中的元素必定不全為NULL或0。
 

之前一直時間超限。。。。把鏈式結構換成了二維數組

然后這個竟然wa掉了,

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 #define MAXN 10
 7 const int maxn=2e6+5;
 8 int Trie[maxn][MAXN];
 9 bool End[maxn];
10 int tot;
11 
12 void init()
13 {
14     for(int i=0;i<tot;i++)
15     {
16         End[i]=false;
17         for(int j=0;j<MAXN;j++)
18         {
19             Trie[i][j]=0;
20         }
21     }
22     tot=0;
23 }
24 
25 int main()
26 {
27     int t;
28     scanf("%d",&t);
29     while(t--)
30     {
31         int n;
32         scanf("%d",&n);
33         getchar();
34         int flag=1; 
35         while(n--)
36         {
37             char str[20];
38             gets(str);
39             int len=strlen(str);
40             int Root=0;
41             for(int i=0;i<len;i++)
42             {
43                 int key=str[i]-0;
44                 if(!Trie[Root][key])
45                     Trie[Root][key]=++tot;
46                 else if(End[Trie[Root][key]]==true)
47                 {
48                     flag=0;
49                 }
50                 Root=Trie[Root][key];
51                 if(i==len-1)
52                     End[Root]=true;
53             }
54             for(int i=0;i<MAXN;i++)
55             {
56                 if(Trie[Root][i]!=0)
57                 {
58                     flag=0;
59                     break;
60                 }
61             }
62         }
63         if(flag)
64             printf("YES\n");
65         else 
66             printf("NO\n");
67         init();
68     }
69     return 0;
70 }

能過的代碼:

极速时时彩走势图首先構造出Trie樹,然后對每個字符串find,當find的路徑上如果出現其他字符串結尾標記,就說明其他字符串是當前字符串的前綴。注意這里對每個字符串find的時候只要搜索到len−1 len-1len−1即可,如果搜索到len lenlen,那么將會將本身的字符串統計進去。

 1 #include<stdio.h>
 2 #include<iostream>
 3 #include<string.h>
 4 using namespace std;
 5 const int maxn =2e6+5;
 6 int tree[maxn][15];
 7 bool flagg[maxn];
 8 int tot;
 9 void insert_(char *str)
10 {
11    int  len=strlen(str);
12    int root=0;
13    for(int i=0;i<len;i++)
14    {
15        int id=str[i]-0;
16        if(!tree[root][id]) tree[root][id]=++tot;
17        root=tree[root][id];
18    }
19    flagg[root]=true;
20 }
21 int find_(char *str)
22 {
23     int len=strlen(str);
24     int root=0;
25     for(int i=0;i<len-1;i++)
26     {
27         int id=str[i]-0;
28         root=tree[root][id];
29         if(flagg[root]) return true;//路徑上出現過其他字符串的結尾標記
30     }
31     return false;
32 }
33 char ss[10005][12];
34 int main()
35 {
36     int n,t;
37     scanf("%d",&t);
38     while(t--)
39     {
40         scanf("%d",&n);
41         for(int i=0;i<n;i++)
42         {
43             scanf("%s",ss[i]);
44             insert_(ss[i]);
45         }
46         int flag=0;
47         for(int i=0;i<n;i++)
48         {
49             if(find_(ss[i]))
50             {
51                 flag=1;
52                 break;
53             }
54         }
55         if(flag==0)
56             printf("YES\n");
57         else
58             printf("NO\n");
59         for(int i=0;i<=tot;i++)
60         {
61             flagg[i]=false;
62             for(int j=0;j<10;j++)
63                 tree[i][j]=0;
64         }
65         tot=0;
66     }
67     return 0;
68 }
69 --------------------- 
70 作者:lajiyuan_ 
71 來源:CSDN 
72 原文:https://blog.csdn.net/qq_38891827/article/details/80532462 
73 版權聲明:本文為博主原創文章,轉載請附上博文鏈接!

 

T9

Description

Background 

A while ago it was quite cumbersome to create a message for the Short Message Service (SMS) on a mobile phone. This was because you only have nine keys and the alphabet has more than nine letters, so most characters could only be entered by pressing one key several times. For example, if you wanted to type "hello" you had to press key 4 twice, key 3 twice, key 5 three times, again key 5 three times, and finally key 6 three times. This procedure is very tedious and keeps many people from using the Short Message Service. 

This led manufacturers of mobile phones to try and find an easier way to enter text on a mobile phone. The solution they developed is called T9 text input. The "9" in the name means that you can enter almost arbitrary words with just nine keys and without pressing them more than once per character. The idea of the solution is that you simply start typing the keys without repetition, and the software uses a built-in dictionary to look for the "most probable" word matching the input. For example, to enter "hello" you simply press keys 4, 3, 5, 5, and 6 once. Of course, this could also be the input for the word "gdjjm", but since this is no sensible English word, it can safely be ignored. By ruling out all other "improbable" solutions and only taking proper English words into account, this method can speed up writing of short messages considerably. Of course, if the word is not in the dictionary (like a name) then it has to be typed in manually using key repetition again. 
      技術圖片
            Figure 8: The Number-keys of a mobile phone.

 More precisely, with every character typed, the phone will show the most probable combination of characters it has found up to that point. Let us assume that the phone knows about the words "idea" and "hello", with "idea" occurring more often. Pressing the keys 4, 3, 5, 5, and 6, one after the other, the phone offers you "i", "id", then switches to "hel", "hell", and finally shows "hello". 

Problem 

极速时时彩走势图Write an implementation of the T9 text input which offers the most probable character combination after every keystroke. The probability of a character combination is defined to be the sum of the probabilities of all words in the dictionary that begin with this character combination. For example, if the dictionary contains three words "hell", "hello", and "hellfire", the probability of the character combination "hell" is the sum of the probabilities of these words. If some combinations have the same probability, your program is to select the first one in alphabetic order. The user should also be able to type the beginning of words. For example, if the word "hello" is in the dictionary, the user can also enter the word "he" by pressing the keys 4 and 3 even if this word is not listed in the dictionary.

Input

The first line contains the number of scenarios. 
Each scenario begins with a line containing the number w of distinct words in the dictionary (0<=w<=1000). These words are given in the next w lines. (They are not guaranteed in ascending alphabetic order, although it‘s a dictionary.) Every line starts with the word which is a sequence of lowercase letters from the alphabet without whitespace, followed by a space and an integer p, 1<=p<=100, representing the probability of that word. No word will contain more than 100 letters. 
Following the dictionary, there is a line containing a single integer m. Next follow m lines, each consisting of a sequence of at most 100 decimal digits 2-9, followed by a single 1 meaning "next word". 

Output

The output for each scenario begins with a line containing "Scenario #i:", where i is the number of the scenario starting at 1. 
For every number sequence s of the scenario, print one line for every keystroke stored in s, except for the 1 at the end. In this line, print the most probable word prefix defined by the probabilities in the dictionary and the T9 selection rules explained above. Whenever none of the words in the dictionary match the given number sequence, print "MANUALLY" instead of a prefix. 
Terminate the output for every number sequence with a blank line, and print an additional blank line at the end of every scenario. 

Sample Input

2
5
hell 3
hello 4
idea 8
next 8
super 3
2
435561
43321
7
another 5
contest 6
follow 3
give 13
integer 6
new 14
program 4
5
77647261
6391
4681
26684371
77771

Sample Output

Scenario #1:
i
id
hel
hell
hello

i
id
ide
idea


Scenario #2:
p
pr
pro
prog
progr
progra
program

n
ne
new

g
in
int

c
co
con
cont
anoth
anothe
another

p
pr
MANUALLY
MANUALLY

 

Hat’s Words

Problem Description

A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.

Input

Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.

Output

Your output should contain all the hat’s words, one per line, in alphabetical order.

Sample Input

a
ahat
hat
hatword
hziee
word

Sample Output

ahat
hatword

 

給出n個按字典序排列的單詞,問其中的所有能由另外兩個單詞組成的單詞并按字典序輸出

(推薦)思路1:先建好字典樹,然后枚舉一個單詞將其拆分成兩個單詞并查詢字典樹中是否有這兩個單詞;

极速时时彩走势图思路2:先把所有的單詞構造成一顆trie圖,然后對所有的單詞進行枚舉,在trie圖上面判斷一個單詞是否由其它兩個單詞構成,具有的做法是先沿著路徑一直走,如果走到某個節點,該節點為一個單詞的結尾,那么再對剩余的單詞再從trie圖的根開始遍歷,看是否能和一個單詞匹配,若匹配成功則該單詞滿足要求,否則繼續進行匹配...

思路3:可以建兩顆Trie樹,然后分別正序倒序插入每個單詞,對每個單詞查詢的時候,分別正序倒序查詢,對出現過單詞的前綴下標進行標記,對每個出現過單詞的后綴進行標記,最后掃描標記數組,如果某個位置前綴后綴均被標記過,則表示可以拆成單詞表中的兩個其他單詞。

 

沒有想到該怎樣枚舉,只想選一個單詞另外兩個怎么選,該弄多少個循環呀,看了別人的方法才知道將這個單詞拆分成兩個單詞;還了解了strncpy,一些字符函數能用則用,本來就是為了方便!

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <string>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #include <algorithm>
  7 using namespace std;
  8 #define MAXN 26
  9 
 10 char word[50005][50];
 11 char ss1[50],ss2[50];
 12 int num;
 13 
 14 struct Trie{
 15     int Flag; 
 16     Trie *Next[MAXN];
 17     Trie()
 18     {
 19         Flag=0;
 20         memset(Next,NULL,sizeof(Next));
 21     }
 22 }*Root;
 23 
 24 void Insert(char *str)
 25 {
 26     Trie *p=Root;
 27     Trie *q=NULL;
 28     int len=strlen(str);
 29     for(int i=0;i<len;i++)
 30     {
 31         int key=str[i]-a;
 32         if(!p->Next[key])
 33         {
 34             q=new Trie();
 35             p->Next[key]=q;
 36         }
 37         p=p->Next[key];
 38         if(i==len-1)
 39         p->Flag=1;
 40     }
 41     return;
 42 } 
 43 
 44 int Qurey(char *str)
 45 {
 46     Trie *p=Root;
 47     int len=strlen(str);
 48     int flag=0;
 49     for(int i=0;i<len;i++)
 50     {
 51         int key=str[i]-a;
 52         if(!p->Next[key])
 53         {
 54             return 0;
 55         }
 56         p=p->Next[key];
 57     }
 58     return p->Flag;
 59 }
 60 
 61 void Find(char *str)
 62 {
 63     int len=strlen(str);
 64     for(int m=1;m<len;m++)
 65     {
 66         //這里用strncmp 
 67         strncpy(ss1,str,m);
 68         ss1[m]=0;
 69         strncpy(ss2,str+m,len-m+1);
 70         ss2[len-m+1]=0;
 71 //      不用strncmp的話 
 72 //        int j=0;
 73 //        for(int i=0;i<m;i++)
 74 //        {
 75 //            ss1[j++]=str[i];
 76 //        }
 77 //        ss1[j]=0;
 78 //        j=0;
 79 //        for(int i=m;i<len;i++)
 80 //        {
 81 //            ss2[j++]=str[i];
 82 //        }
 83 //        ss2[j]=0;
 84         //printf("ss1=%s ss2=%s\n",ss1,ss2);
 85         if(Qurey(ss1)&&Qurey(ss2))
 86         {
 87             puts(str);
 88             break;   //不帶break;就wa掉了,無語 
 89         }
 90     }
 91 }
 92 
 93 void Free(Trie *T)
 94 {
 95     if(T==NULL) return;
 96     for(int i=0;i<MAXN;i++)
 97     {
 98         if(T->Next[i]) Free(T->Next[i]);
 99     }
100     delete(T);
101 }
102 
103 int main()
104 {
105     freopen("sampletem.txt","r",stdin);
106     char str[50];
107     Root=new Trie();
108     while(~scanf("%s",str))
109     {
110         strcpy(word[num++],str);
111         Insert(str);
112     }
113     for(int i=0;i<num;i++)
114     {
115         Find(word[i]);
116     }
117     Free(Root);
118     return 0;
119 }

 

 

What Are You Talking About

Problem Description

极速时时彩走势图Ignatius is so lucky that he met a Martian yesterday. But he didn‘t know the language the Martians use. The Martian gives him a history book of Mars and a dictionary when it leaves. Now Ignatius want to translate the history book into English. Can you help him?

Input

The problem has only one test case, the test case consists of two parts, the dictionary part and the book part. The dictionary part starts with a single line contains a string "START", this string should be ignored, then some lines follow, each line contains two strings, the first one is a word in English, the second one is the corresponding word in Martian‘s language. A line with a single string "END" indicates the end of the directory part, and this string should be ignored. The book part starts with a single line contains a string "START", this string should be ignored, then an article written in Martian‘s language. You should translate the article into English with the dictionary. If you find the word in the dictionary you should translate it and write the new word into your translation, if you can‘t find the word in the dictionary you do not have to translate it, and just copy the old word to your translation. Space(‘ ‘), tab(‘\t‘), enter(‘\n‘) and all the punctuation should not be translated. A line with a single string "END" indicates the end of the book part, and that‘s also the end of the input. All the words are in the lowercase, and each word will contain at most 10 characters, and each line will contain at most 3000 characters.

Output

In this problem, you have to output the translation of the history book.
 

Sample Input

START
from fiwo
hello difh
mars riwosf
earth fnnvk
like fiiwj
END
START
difh, im fiwo riwosf.
i fiiwj fnnvk!
END

Sample Output

hello, im from mars.
i like earth!

Hint

Huge input, scanf is recommended.

 

本題的題意是給你火星文與地球文的映射方式,然后給你一個火星文組成的文本,若某單詞在映射文本中出現過,則輸出映射之后的文本。否則輸出原文本

字典樹,經典題,字典翻譯。
  WA了1次,后來發現是我把要翻譯的單詞搞錯了,如果一個可以翻譯的較長的單詞包含著另一個可以翻譯的較短的單詞,這樣遍歷句子的時候就會先碰到較短的單詞,WA的程序會先把這個短單詞翻譯出來,但實際上這是不對的,應該翻譯整個較長的單詞,而不是遇到什么就翻譯什么。
  我的程序運行時間是281MS,用鏈表做的,用數組應該會快些。
  題意
  只有一組測試數據,分成兩部分。第一部分是字典,給你若干個單詞以及對應的翻譯,以START開始,END結束;第二部分是翻譯部分,給你若干句子,要求你根據上面給出的字典,將火星文翻譯成英文,以START開始,END結束。這里翻譯的時候,要注意只有字典中有對應翻譯的單詞才翻譯,字典中沒有對應翻譯的單詞以及標點符號空格原樣輸出。
  思路
  將字典中的火星文單詞,也就是右邊的單詞構造成一棵字典樹。在單詞結束的節點中存儲其對應的英文翻譯。輸入的時候讀取整行,然后遍歷每一個字符,將所有字母連續的記錄到一個字符數組中,直到遇到一個非英文字母的字符為止,這個時候從字典樹中查找這個單詞有沒有對應的英文翻譯,如果有,輸出這個翻譯,如果沒有,輸出原來的單詞。
  注意
  1.輸入方法,使用的scanf+gets。
  2.不要搞錯要翻譯的單詞,遇到一個非字母的字符算一個單詞。
  3.盡量不要使用cin,cout,容易超時
  1 #include <cstdio>
  2 #include <iostream>
  3 #include <string>
  4 #include <string.h>
  5 #include <stdlib.h>
  6 #include <algorithm>
  7 using namespace std;
  8 #define MAXN 26
  9 string fin="";
 10 
 11 struct Trie{
 12     int Flag; 
 13     Trie *Next[MAXN];
 14     string chc;
 15     Trie()
 16     {
 17         Flag=0;
 18         memset(Next,NULL,sizeof(Next));
 19     }
 20 }*Root;
 21 
 22 void Insert(string str,string ss)
 23 {
 24     Trie *p=Root;
 25     Trie *q=NULL;
 26     int len=str.size();
 27     for(int i=0;i<len;i++)
 28     {
 29         int key=str[i]-a;
 30         if(!p->Next[key])
 31         {
 32             q=new Trie();
 33             p->Next[key]=q;
 34         }
 35         p=p->Next[key];
 36         if(i==len-1)
 37         p->Flag=1;
 38         p->chc=ss;
 39     }
 40     return;
 41 } 
 42 
 43 void Qurey(string str)
 44 {
 45     Trie *p=Root;
 46     int len=str.size();
 47     int flag=0;
 48     for(int i=0;i<len;i++)
 49     {
 50         int key=str[i]-a;
 51         if(!p->Next[key])
 52         {
 53             flag=1;
 54             break;
 55         }
 56         else
 57             p=p->Next[key];
 58         if(i==len-1&&p->Flag==1)
 59             fin+=p->chc; 
 60     }
 61     if(flag||p->Flag!=1)
 62         fin+=str;
 63     return;
 64 }
 65 
 66 int main()
 67 {
 68     //freopen("sampletem.txt","r",stdin);
 69     string a,b;
 70     Root=new Trie();
 71     cin>>a;
 72     while(cin>>a)
 73     {
 74         if(a[0]==E)
 75             break;
 76         cin>>b;
 77         Insert(b,a);
 78     }
 79     cin>>a;
 80     getchar();
 81     char c;
 82     string tem="";
 83     while(c=getchar())
 84     {
 85         if(c==E)
 86         {
 87             c=getchar();
 88             c=getchar();
 89             break;
 90         }
 91         else if(c>=a&&c<=z)
 92         {
 93             tem+=c;
 94         }
 95         else 
 96         {
 97             if(tem!="")
 98                 Qurey(tem);
 99             fin+=c;
100             tem="";
101         }
102     }
103     cout<<fin;
104     return 0;
105 }

 

 

 

Tire樹(字典樹)

標簽:sms   can   space   join   ext   空間換時間   拆分   guarantee   sdn   

原文地址:https://www.cnblogs.com/jiamian/p/11152493.html

(0)
(0)
   
舉報
評論 一句話評論(0
0條  
登錄后才能評論!
           
? 2014 mamicode.com 版權所有 京ICP備13008772號-2
迷上了代碼!