今天AC了兩題trie tree的題目,感覺trie的性質(zhì)真的是相當(dāng)?shù)暮茫覍?shí)現(xiàn)比較簡單。它使在字符串集合中查找某個(gè)字符串的操作的復(fù)雜度降到最大只需O(n),其中n為字符串的長度。trie是典型的將時(shí)間置換為空間的算法，好在ACM中一般對空間的要求很寬松。

     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為字符串長度。

    舉一個(gè)例子,給50000個(gè)由小寫字母構(gòu)成的長度不超過10的單詞,然后問某個(gè)公共前綴是否出現(xiàn)過。如果我們直接從字符串集中從頭往后搜，看給定的字符串是否為字符串集中某個(gè)字符串的前綴，那樣復(fù)雜度為O(50000^2)，這樣顯然會(huì)TLE。又或是我們對于字符串集中的每個(gè)字符串，我們用MAP存下它所有的前綴。然后詢問時(shí)可以直接給出結(jié)果。這樣復(fù)雜度為O(50000*len),最壞情況下len為字符串最長字符串的長度。而且這沒有算建立MAP存儲(chǔ)的時(shí)間，也沒有算用MAP查詢的時(shí)間，實(shí)際效率會(huì)更低。但如果我們用trie的話，當(dāng)查詢?nèi)缱址?/span>abcd是否為某字符串的前綴時(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í)，對應(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級數(shù)。(誰有好辦法降低空間開銷,請告訴我)

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

題目:http://acm.hdu.edu.cn/showproblem.php?pid=1251

題目和我上面舉的例子差不多，是說給定一個(gè)字符串集合，然后每次詢問時(shí)給出一個(gè)字符串，問以該字符串為前綴的字符串在集合中有多少個(gè)。先給個(gè)用MAP版本的，限時(shí)2000MS的題目，用MAP，1750MS，險(xiǎn)過。