字典树Trie树的应用

问题：有若干个字符串，求他们的最长公共前缀子串。

解法：该问题的一个比较好的办法是使用Trie树。因为Trie树有明显的字符串前缀特征。在查询近似前缀的时候经常用到。这里我建立了Trie树，且为了寻找最长公共前缀子串更方便，对结点加入了分支个数属性branch和出现次数属性times。这样，把所有字符串加入Trie树之后，通过根结点出发寻找单分支路径且出现次数均为字符串集个数，就可以找到结果。

代码：

[cpp]view plaincopy 
   
 #include <string>  
 #include <iostream>  
 #include <vector>  
 #include <malloc.h>  
 using namespace std;  
 #define N 26  
   
 typedef struct node {   
     char ch;  
     int branch ; //记录分支树，方便最后查询  
     int times;  
     node* child[N];  
 }node, *Trie;  
   
 Trie init_Trie()  
 {  
     Trie root = (node*)malloc(sizeof(node)); //Trie树的根节点不存储数据  
     root->branch = 0;  
     root->times = 0;  
     for(int i=0;i<N;i++)  
         root->child[i] = NULL;  
     return root;  
 }  
   
 void insert_Trie(Trie root, const string str)  
 {  
     int n = str.length();  
     if(n == 0)  
     {  
         root->times ++;  
         return;  
     }  
     int i=0;  
     int idx;  
     node *p = root;  
     root->times++;  
     while(i<n)  
     {  
         idx = str[i] - 'a';  
         if(p->child[idx] != NULL)  
         {  
             p = p->child[idx];  
             p->times ++;  
             i++;  
         }  
         else  
         {  
             node* tmp = (node*)malloc(sizeof(node));  
             tmp->ch = str[i];  
             tmp->branch = 0;  
             tmp->times = 1;  
             for(int j=0;j<N;j++)  
                 tmp->child[j] = NULL;  
   
             p->branch ++;  
             p->child[idx] = tmp;  
             p = tmp;  
             i++;  
         }  
     }  
 }  
   
 string longestCommonPrefix(vector<string> &strs)  
 {  
     int n = strs.size();  
     if(n == 0)  
         return "";  
   
     int i;  
     Trie root = init_Trie();  
     for(i=0;i<n;i++)  
         insert_Trie(root, strs[i]);  
   
     i = 0;  
     node* p = root;  
     while(i<strs[0].length() && p->branch == 1 && p->times == n)  
     {  
         p = p->child[strs[0][i] - 'a'];  
         i++;  
     }  
     if(p->times < n)  
         i--;  
     return strs[0].substr(0,i);  
 }  
   
 int main()  
 {  
     vector<string> strs;  
     strs.push_back("a");  
     strs.push_back("aa");  
     //strs.push_back("abcd");  
     string result = longestCommonPrefix(strs);  
     cout<<result<<endl;  
     return 1;  
 }  

字典树Trie树的应用

浏览过的版块