Trie樹 學(xué)習(xí)感受
相比于之前學(xué)習(xí)的kmp匹配算法，Trie樹的實現(xiàn)還是非常好理解的。（kmp算法太難了orz）
從直觀的模擬過程來看，trie樹就像一顆樹一樣，從上（根節(jié)點）到下（葉節(jié)點）有序串聯(lián)起來組成一個字符串。
每一個額外標記結(jié)束的位置表示字符串的結(jié)束，通過計算標記數(shù)即可指導(dǎo)一共有多少該字符串。
?
?
從暴力算法看Trie算法
先想想，如果要是暴力算法來做的話，應(yīng)該怎么去統(tǒng)計字符串出現(xiàn)次數(shù)呢？
首先要利用數(shù)組去存儲各種不相同的字符串，在讀入一個新的字符串時，需要先判斷他和已有的字符串是否相等，如果不相等，則將該字符串存入，如果相等，則跳過該字符串。顯然，暴力算法的時間復(fù)雜度會很大。在這里，有沒有更好的判斷方法，讓我不用再去每次判斷都要遍歷所有已經(jīng)儲存的字符串呢？
我們來著重討論判斷他和已有字符串是否相等，在這里的判斷方法顯然是循環(huán)遍歷兩個字符串，判斷字符串長度以及每個位置是否相等。那么，在循環(huán)遍歷所有字符串的過程中，不難發(fā)現(xiàn)，對于部分相等以及完全相等字符串，從字符串第一個字符起，總會和目標字符串有一個公共部分。那么，我們是否可以對于字符串每一個位置（對于數(shù)的每一層）只存儲一個字符串該位置出現(xiàn)的字符，使得所有字符串共用一顆樹（如上圖）。這樣在大大減少時間復(fù)雜度的同時，空間復(fù)雜度也得到的減小。
Trie樹的實現(xiàn)
Trie樹的實現(xiàn)過程是用數(shù)組模擬實現(xiàn)多叉樹的過程。首先需要一個二維數(shù)組 trie[n][m] 來實現(xiàn)樹。其中 n 代表所有字符的總長度，m代表多叉樹的最大分支。
再者，需要一個 cnt[n] 數(shù)組存儲每個字符串出現(xiàn)的次數(shù)，n應(yīng)該小于所有字符的總數(shù)量。
最后，需要一個整型變量 idx ， 用于存儲樹中某個節(jié)點對應(yīng) cnt 數(shù)組的下標。
?
樹的插入代碼如下：
void insert(string s) { int tmp = 0;//tmp 代表當(dāng)前節(jié)點的位置，0 代表根節(jié)點 for(auto c : s) { int u = c - 'a';//將二十六個字母映射到0到25 if(!trie[tmp][u]) trie[tmp][u] = ++ idx;//如果字典樹當(dāng)前位置當(dāng)中沒有這個字符，則建立這個字符，且將他與cnt數(shù)組對應(yīng) tmp = trie[tmp][u];//類比指針，指向字典樹下一個位置 } cnt[tmp] ++;//把字符串結(jié)束對應(yīng)的點的計數(shù)數(shù)組增加一 }
樹的查詢代碼如下：文章來源：http://www.zghlxwxcb.cn/news/detail-474495.html
int search(string s) { int tmp = 0;//tmp 代表當(dāng)前節(jié)點的位置，0 代表根節(jié)點 for(auto c : s) { int u = c - 'a';//將二十六個字母映射到0到25 if(!trie[tmp][u]) return 0;//如果字典樹當(dāng)前位置當(dāng)中沒有這個字符，則查詢結(jié)束，證明沒有這個字符串 else tmp = trie[tmp][u];//類比指針，指向字典樹下一個位置 } return cnt[tmp];//返回該字符串的個數(shù) }
?文章來源地址http://www.zghlxwxcb.cn/news/detail-474495.html
到了這里，關(guān)于【acwing】Trie字符串統(tǒng)計的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
