今天AC了兩題trie tree的題目,感覺trie的性質(zhì)真的是相當(dāng)?shù)暮茫覍?shí)現(xiàn)比較簡(jiǎn)單。它使在字符串集合中查找某個(gè)字符串的操作的復(fù)雜度降到最大只需O(n),其中n為字符串的長(zhǎng)度。trie是典型的將時(shí)間置換為空間的算法，好在ACM中一般對(duì)空間的要求很寬松。
trie的原理是利用字符串集合中字符串的公共前綴來降低時(shí)間開銷以達(dá)到提高效率的目的。
它具有以下性質(zhì):1,根結(jié)點(diǎn)不包含任何字符信息;2,如果字符的種數(shù)為n,則每個(gè)結(jié)點(diǎn)的出度為n(這樣必然會(huì)導(dǎo)致浪費(fèi)很多空間,這也是trie的缺點(diǎn),我還沒有想到好點(diǎn)的辦法避免);3,查找，插入復(fù)雜度為O(n),n為字符串長(zhǎng)度。
舉一個(gè)例子,給50000個(gè)由小寫字母構(gòu)成的長(zhǎng)度不超過10的單詞,然后問某個(gè)公共前綴是否出現(xiàn)過。如果我們直接從字符串集中從頭往后搜，看給定的字符串是否為字符串集中某個(gè)字符串的前綴，那樣復(fù)雜度為O(50000^2)，這樣顯然會(huì)TLE。又或是我們對(duì)于字符串集中的每個(gè)字符串，我們用MAP存下它所有的前綴。然后詢問時(shí)可以直接給出結(jié)果。這樣復(fù)雜度為O(50000*len),最壞情況下len為字符串最長(zhǎng)字符串的長(zhǎng)度。而且這沒有算建立MAP存儲(chǔ)的時(shí)間，也沒有算用MAP查詢的時(shí)間，實(shí)際效率會(huì)更低。但如果我們用trie的話，當(dāng)查詢?nèi)缱址產(chǎn)bcd是否為某字符串的前綴時(shí)，顯然以b,c,d....等不是以a開頭的字符串就不用查找了。實(shí)際查詢復(fù)雜度只有O(len)，建立trie的復(fù)雜度為O(50000).這是完全可以接受的。
如給定字符串集合abcd,abd,cdd,efg,hij,hi六個(gè)字符串建立的trie tree如下圖所示:
查找一個(gè)字符串時(shí)，我們只需從根結(jié)點(diǎn)按字符串中字符出現(xiàn)順序依次往下走。如果到最后字符串結(jié)束時(shí)，對(duì)應(yīng)的結(jié)點(diǎn)標(biāo)記為紅色，則該字符串存在;否則不存在。
插入時(shí)也只需從根結(jié)點(diǎn)往下遍歷，碰到已存在的字符結(jié)點(diǎn)就往下遍歷，否則，建立新結(jié)點(diǎn);最后標(biāo)記最后一個(gè)字符的結(jié)點(diǎn)為紅色即可。
同時(shí)我們看到,如果字符的種類為n，則需要結(jié)點(diǎn)的個(gè)數(shù)為n級(jí)數(shù)。(誰(shuí)有好辦法降低空間開銷,請(qǐng)告訴我)
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
題目和我上面舉的例子差不多，是說給定一個(gè)字符串集合，然后每次詢問時(shí)給出一個(gè)字符串，問以該字符串為前綴的字符串在集合中有多少個(gè)。先給個(gè)用MAP版本的，限時(shí)2000MS的題目，用MAP，1750MS，險(xiǎn)過。
my code1:
|
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
int i,j,k,len;
string str;char temp[15],temp1[15];
map <string,int> mymap;
while(gets(temp))
{
if(temp[0]=='\n') break;
len=strlen(temp);
if(len==0) break;
for(i=0;i<len;i++)//求出某個(gè)字符串的所有前綴,并用MAP存起來
{
for(j=0;j<=i;j++) temp1[j]=temp[j];temp1[j]='\0';
str.assign(temp1);
mymap[str]++;
}
}
while(scanf("%s",&temp)!=EOF)
cout<<mymap[temp]<<endl;//此時(shí)直接輸出結(jié)果即可
return 0;
}
|
用MAP的特點(diǎn)是代碼短，思路簡(jiǎn)單，很容易實(shí)現(xiàn)，但耗時(shí)大。下面給出trie版本的。
my code2:
|
#include<iostream>
using namespace std;
const int kind=26;//字母種類
struct Treenode//樹的結(jié)點(diǎn)結(jié)構(gòu)
{
int count;//這個(gè)附加變量在本題中記錄遍歷到該結(jié)點(diǎn)形成的字符串出現(xiàn)的次數(shù)，在不同題中可記錄不同的內(nèi)容。
Treenode *next[kind];//指向兒子結(jié)點(diǎn)
Treenode()//每個(gè)結(jié)點(diǎn)的初始化
{
count=1;
for(int i=0;i<kind;i++)
next[i]=NULL;
}
};
void insert(Treenode *&root,char *word)//向以root為根結(jié)點(diǎn)的樹中插入串word
{
Treenode *location=root;
int i=0,branch=0;
if(location==NULL) {location=new Treenode();root=location;}
while(word[i])
{
branch=word[i]-'a';
if(location->next[branch]) location->next[branch]->count++;//如果該字符存在，串?dāng)?shù)量加1
else location->next[branch]=new Treenode();//如果不存在，建新結(jié)點(diǎn)
i++;
location=location->next[branch];
}
}
int search(Treenode *root,char *word)//查找，與插入類似
{
Treenode *location=root;
int i=0,branch=0,ans;
if(location==NULL) return 0;
while(word[i])
{
branch=word[i]-'a';
if(!location->next[branch]) return 0;
i++;
location=location->next[branch];
ans=location->count;
}
return ans;
}
int main()
{
char word[10];
char ask[10];
Treenode *root=NULL;
while(gets(word))
{
if(word[0]=='\0') break;
insert(root,word);
}
while(gets(ask))
cout<<search(root,ask)<<endl;
return 0;
}
|
上述代碼中插入和查找可當(dāng)模板來用了。。。