? ? 1Trie樹

????????這節(jié)課學(xué)習(xí)了一種特殊的樹，Trie樹。Trie樹是一種解決字符串快速匹配問題的數(shù)據(jù)結(jié)構(gòu)。如果用來構(gòu)建Trie樹的這一組字符串中，前綴重復(fù)的情況并不是很多，那Trie樹這種數(shù)據(jù)結(jié)構(gòu)總體上來講是比較費(fèi)內(nèi)存的，是一種空間換時(shí)間的解決問題思路。

? ? ? ? 盡管比較耗費(fèi)內(nèi)存，但是對內(nèi)存不敏感或者內(nèi)存消耗在接受范圍內(nèi)的情況下，在Trie樹中做字符串匹配還是非常高效的，時(shí)間復(fù)雜度是O(k)，k表示要匹配的字符串的長度。

? ? ? ? 但是，Trie樹的優(yōu)勢并不在于，用它來做動(dòng)態(tài)集合數(shù)據(jù)的查找，因?yàn)檫@個(gè)工作完全可以由更加合適的散列表或者紅黑樹來替代。Trie樹最有優(yōu)勢的是查找前綴匹配的字符串，比如搜索引擎中的關(guān)鍵詞提示功能這個(gè)場景，就比較適合用它來解決，也是Trie樹比較經(jīng)典的應(yīng)用場景。??

????2AC自動(dòng)機(jī)

? ? ? ? 這節(jié)課學(xué)習(xí)了多模式串匹配算法，AC自動(dòng)機(jī)。單模式串匹配算法是為了快速在主串中查找一個(gè)模式串，而多模式串匹配算法是為了快速在主串中查找多個(gè)模式串。

? ? ? ? AC自動(dòng)機(jī)是基于Trie樹的一種改進(jìn)算法，它跟Trie樹的關(guān)系，就像單模式串中KMP算法和BF算法的關(guān)系一樣。KMP算法中有一個(gè)非常關(guān)鍵的next數(shù)組，類比到AC自動(dòng)機(jī)中就是失敗指針。而且，AC自動(dòng)機(jī)失敗指針的構(gòu)建過程，跟KMP算法中計(jì)算next數(shù)組極其相似。所以，要理解AC自動(dòng)機(jī)，最好先掌握KMP算法，因?yàn)锳C自動(dòng)機(jī)其實(shí)就是KMP算法在多模式串上的改造。

? ? ? ? 整個(gè)AC自動(dòng)機(jī)算法包含兩個(gè)部分：第一部分是將多個(gè)模式串構(gòu)建成AC自動(dòng)機(jī)，第二部分是在AC自動(dòng)機(jī)中匹配子串。第一部分又分為兩個(gè)小的步驟，一個(gè)是將模式串構(gòu)建成Trie樹，另一個(gè)是在Trie樹上構(gòu)建失敗指針。