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