\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2015年1月10日 星期六

字典樹 Trie

今天完成了字典樹 Trie的模板,可以在O(N) (N=字串長度)的時間搜尋一個字串
插入的時間亦是O(N),在字串匹配上有很大的幫助(AC字動機),但是因為每個節點都要記錄所有字元,是非常耗空間的
通常將根節點設為"沒有字元",若是想進一步了解Trie請自行google吧!
以下為模板:
跟stl map的用法類似
trie<int >t;  //定義一個存int的Trie
trie<int ,'a','z'>t  //定義一個字元範圍是'a'到'z'的Trie(預設是'A'~'z')
trie<int >::point_iterator it;  //定義一個節點迭代器
t.insert("asd",1);  //插入1到"asd"的位置(若原來已有值則覆蓋),傳回插入節點的point_iterator
t.find("asd");  //傳回"asd"位置的point_iterator,若無資料point_iterator為NULL,請注意
t["asf"];  //若"asd"存在資料,傳回其引用位置,若不存在則插入並傳回其引用位置
t.erase("asd");  //刪除"asd"節點,若成功刪除則傳回true,失敗(無結點)則傳回false
t.size(); //傳回字串的總數
t.clear();  //清空trie

沒有留言:

張貼留言