今天AC了兩題trie tree的題目,感覺trie的性質(zhì)真的是相當(dāng)?shù)暮茫覍崿F(xiàn)比較簡單。它使在字符串集合中查找某個字符串的操作的復(fù)雜度降到最大只需O(n),其中n為字符串的長度。trie是典型的將時間置換為空間的算法，好在ACM中一般對空間的要求很寬松。
trie的原理是利用字符串集合中字符串的公共前綴來降低時間開銷以達到提高效率的目的。
它具有以下性質(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)模板來用了。。。