**一、知識簡介** ???? 最近在看字符串算法了，其中字典樹、AC自動機和后綴樹的應用是最廣泛的了，下面將會重點介紹下這幾個算法的應用。 ???? 字典樹（Trie）可以保存一些字符串->值的對應關系。基本上，它跟 Java 的 HashMap 功能相同，都是 key-value 映射，只不過 Trie 的 key 只能是字符串。 　　Trie 的強大之處就在于它的時間復雜度。它的插入和查詢時間復雜度都為 O(k) ，其中 k 為 key 的長度，與 Trie 中保存了多少個元素無關。Hash 表號稱是 O(1) 的，但在計算 hash 的時候就肯定會是 O(k) ，而且還有碰撞之類的問題；Trie 的缺點是空間消耗很高。 　　至于Trie樹的實現，可以用數組，也可以用指針動態分配，我做題時為了方便就用了數組，靜態分配空間。 ???? Trie樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計和排序大量的字符串（但不僅限于字符串），所以經常被搜索引擎系統用于文本詞頻統計。它的優點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。 ???? Trie的核心思想是空間換時間。利用字符串的公共前綴來降低查詢時間的開銷以達到提高效率的目的。 Trie樹的基本性質可以歸納為： （1）根節點不包含字符，除根節點意外每個節點只包含一個字符。 （2）從根節點到某一個節點，路徑上經過的字符連接起來，為該節點對應的字符串。 （3）每個節點的所有子節點包含的字符串不相同。 Trie樹有一些特性： 1）根節點不包含字符，除根節點外每一個節點都只包含一個字符。 2）從根節點到某一節點，路徑上經過的字符連接起來，為該節點對應的字符串。 3）每個節點的所有子節點包含的字符都不相同。 4）如果字符的種數為n，則每個結點的出度為n，這也是空間換時間的體現，浪費了很多的空間。 5）插入查找的復雜度為O(n)，n為字符串長度。 基本思想（以字母樹為例）： 1、插入過程 對于一個單詞，從根開始，沿著單詞的各個字母所對應的樹中的節點分支向下走，直到單詞遍歷完，將最后的節點標記為紅色，表示該單詞已插入Trie樹。 2、查詢過程 同樣的，從根開始按照單詞的字母順序向下遍歷trie樹，一旦發現某個節點標記不存在或者單詞遍歷完成而最后的節點未標記為紅色，則表示該單詞不存在，若最后的節點標記為紅色，表示該單詞存在。 二、字典樹的數據結構： ?? 利用串構建一個字典樹，這個字典樹保存了串的公共前綴信息，因此可以降低查詢操作的復雜度。 ?? 下面以英文單詞構建的字典樹為例，這棵Trie樹中每個結點包括26個孩子結點，因為總共有26個英文字母(假設單詞都是小寫字母組成)。 ?? 則可聲明包含Trie樹的結點信息的結構體: ~~~ typedef struct Trie_node { int count; // 統計單詞前綴出現的次數 struct Trie_node* next[26]; // 指向各個子樹的指針 bool exist; // 標記該結點處是否構成單詞 }TrieNode , *Trie; ~~~ ???? 其中next是一個指針數組，存放著指向各個孩子結點的指針。 ???? 如給出字符串"abc","ab","bd","dda"，根據該字符串序列構建一棵Trie樹。則構建的樹如下:  Trie樹的根結點不包含任何信息，第一個字符串為"abc"，第一個字母為'a'，因此根結點中數組next下標為'a'-97的值不為NULL，其他同理，構建的Trie樹如圖所示，紅色結點表示在該處可以構成一個單詞。很顯然，如果要查找單詞"abc"是否存在，查找長度則為O(len)，len為要查找的字符串的長度。而若采用一般的逐個匹配查找，則查找長度為O(len*n)，n為字符串的個數。顯然基于Trie樹的查找效率要高很多。 如上圖中：Trie樹中存在的就是abc、ab、bd、dda四個單詞。在實際的問題中可以將標記顏色的標志位改為數量count等其他符合題目要求的變量。 已知n個由小寫字母構成的平均長度為10的單詞，判斷其中是否存在某個串為另一個串的前綴子串。下面對比3種方法： 1、 最容易想到的：即從字符串集中從頭往后搜，看每個字符串是否為字符串集中某個字符串的前綴，復雜度為O(n^2)。 2、 使用hash：我們用hash存下所有字符串的所有的前綴子串。建立存有子串hash的復雜度為O(n*len)。查詢的復雜度為O(n)* O(1)= O(n)。 3、 使用Trie：因為當查詢如字符串abc是否為某個字符串的前綴時，顯然以b、c、d....等不是以a開頭的字符串就不用查找了，這樣迅速縮小查找的范圍和提高查找的針對性。所以建立Trie的復雜度為O(n*len)，而建立+查詢在trie中是可以同時執行的，建立的過程也就可以成為查詢的過程，hash就不能實現這個功能。所以總的復雜度為O(n*len)，實際查詢的復雜度只是O(len)。 **三、Trie樹的操作** ?? 在Trie樹中主要有3個操作，插入、查找和刪除。一般情況下Trie樹中很少存在刪除單獨某個結點的情況，因此只考慮刪除整棵樹。 1、插入 假設存在字符串str，Trie樹的根結點為root。i=0，p=root。 1)取str[i]，判斷p->next[str[i]-97]是否為空，若為空，則建立結點temp，并將p->next[str[i]-97]指向temp，然后p指向temp； 若不為空，則p=p->next[str[i]-97]； 2)i++，繼續取str[i]，循環1)中的操作，直到遇到結束符'\0'，此時將當前結點p中的 exist置為true。 2、查找 假設要查找的字符串為str，Trie樹的根結點為root，i=0，p=root 1)取str[i]，判斷判斷p->next[str[i]-97]是否為空，若為空，則返回false；若不為空，則p=p->next[str[i]-97]，繼續取字符。 2)重復1)中的操作直到遇到結束符'\0'，若當前結點p不為空并且 exist 為true，則返回true，否則返回false。 3、刪除 刪除可以以遞歸的形式進行刪除。 前綴查詢的典型應用： [http://acm.hdu.edu.cn/showproblem.php?pid=1251](http://acm.hdu.edu.cn/showproblem.php?pid=1251) ~~~ #include<iostream> #include<cstring> using namespace std; typedef struct Trie_node { int count; // 統計單詞前綴出現的次數 struct Trie_node* next[26]; // 指向各個子樹的指針 bool exist; // 標記該結點處是否構成單詞 }TrieNode , *Trie; TrieNode* createTrieNode() { TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode)); node->count = 0; node->exist = false; memset(node->next , 0 , sizeof(node->next)); // 初始化為空指針 return node; } void Trie_insert(Trie root, char* word) { Trie node = root; char *p = word; int id; while( *p ) { id = *p - 'a'; if(node->next[id] == NULL) { node->next[id] = createTrieNode(); } node = node->next[id]; // 每插入一步，相當于有一個新串經過，指針向下移動 ++p; node->count += 1; // 這行代碼用于統計每個單詞前綴出現的次數（也包括統計每個單詞出現的次數） } node->exist = true; // 單詞結束的地方標記此處可以構成一個單詞 } int Trie_search(Trie root, char* word) { Trie node = root; char *p = word; int id; while( *p ) { id = *p - 'a'; node = node->next[id]; ++p; if(node == NULL) return 0; } return node->count; } int main(void) { Trie root = createTrieNode(); // 初始化字典樹的根節點 char str[12] ; bool flag = false; while(gets(str)) { if(flag) printf("%d\n",Trie_search(root , str)); else { if(strlen(str) != 0) { Trie_insert(root , str); } else flag = true; } } return 0; } ~~~ 字典樹的查找 [http://acm.hdu.edu.cn/showproblem.php?pid=1075](http://acm.hdu.edu.cn/showproblem.php?pid=1075) ~~~ #include<iostream> #include<cstring> using namespace std; typedef struct Trie_node { int count; // 統計單詞前綴出現的次數 struct Trie_node* next[26]; // 指向各個子樹的指針 bool exist; // 標記該結點處是否構成單詞 char trans[11]; // 翻譯 }TrieNode , *Trie; TrieNode* createTrieNode() { TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode)); node->count = 0; node->exist = false; memset(node->next , 0 , sizeof(node->next)); // 初始化為空指針 return node; } void Trie_insert(Trie root, char* word , char* trans) { Trie node = root; char *p = word; int id; while( *p ) { id = *p - 'a'; if(node->next[id] == NULL) { node->next[id] = createTrieNode(); } node = node->next[id]; // 每插入一步，相當于有一個新串經過，指針向下移動 ++p; node->count += 1; // 這行代碼用于統計每個單詞前綴出現的次數（也包括統計每個單詞出現的次數） } node->exist = true; // 單詞結束的地方標記此處可以構成一個單詞 strcpy(node->trans , trans); } char* Trie_search(Trie root, char* word) { Trie node = root; char *p = word; int id; while( *p ) { id = *p - 'a'; node = node->next[id]; ++p; if(node == NULL) return 0; } if(node->exist) // 查找成功 return node->trans; else // 查找失敗 return NULL; } int main(void) { Trie root = createTrieNode(); // 初始化字典樹的根節點 char str1[3003] , str2[3003] , str[3003] , *p; int i , k; scanf("%s",str1); while(scanf("%s",str1) && strcmp(str1 , "END") != 0) { scanf("%s",str2); Trie_insert(root , str2 , str1); } getchar(); gets(str1); k = 0; while(gets(str1)) { if(strcmp(str1 , "END") == 0) break; for(i = 0 ; str1[i] != '\0' ; ++i) { if(str1[i] >= 'a' && str1[i] <= 'z') { str[k++] = str1[i]; } else { str[k] = '\0'; p = Trie_search(root , str); if(p) printf("%s", p); else printf("%s", str); k = 0; printf("%c", str1[i]); } } printf("\n"); } return 0; } ~~~