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