• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>


            如圖,每條路徑上保存一個字母,從根節點開始進行dfs,每遍歷到一個標記節點(圖中的紅點),從根節點到當前節點路徑上所有字母連起來即為一個單詞

            上圖中存儲了 abc, abcd, b, bcd, efg, hij.

            對于Trie樹主要有三種操作:

            1. 新建一個結點
            2. 插入一個單詞
            3. 在trie樹中查找單詞
            trie樹中每次插入一個結點的時間復雜度是 O( strlen( str ) )
            建立trie樹的時間復雜度為 O( ∑strlen( str[i] ) )
            對于每個單詞,查詢的時間復雜度為 O( strlen( str ) )

            Templates:

            Struct:

            struct node  
            {  
                
            int flag;     //The end of a word  
                node* next[26];  
            };  

            新建結點:

            node* newnode()  
            {  
                node* p = new node;  
              
                p->flag = 0;  
              
                
            forint i = 0; i < 26; i++ )  
                    p->next[i] = NULL;  
              
                
            return p;  
            }  

            插入單詞:

            void trie_insert( node* root, char* s )  
            {  
                node* p = root;  
                
            int len = strlen( s );  
              
                
            int tmp;  
                
            forint i = 0; i < len; i++ )  
                {  
                    tmp = s[i] - 'a';  
                    
            if( p->next[tmp] == NULL )  
                        p->next[tmp] = newnode();  
                    p = p->next[tmp];  
                }  
                p->flag = 1;  
            }  

            查詢:

            int trie_search( node* root, char* s )  
            {  
                node* p = root;  
                
            int len = strlen( s );  
              
                
            int tmp;  
                
            forint i = 0; i < len; i++ )  
                {  
                    tmp = s[i] - 'a';  
                    
            if( p->next[tmp] == NULL )         //not matched  
                        return 0;  
                    p = p->next[tmp];  
                }  
              
                
            if( p->flag )     //match && it is a word which has been stored  
                return 1;  
                
            return 0;  
            }  
            posted on 2016-08-31 09:35 Vontroy 閱讀(370) 評論(0)  編輯 收藏 引用 所屬分類: 字符串
            99久久精品无码一区二区毛片 | 综合久久精品色| 亚洲国产成人精品女人久久久 | 久久er国产精品免费观看8| 一级女性全黄久久生活片免费| 99久久综合国产精品二区| 久久成人小视频| 亚洲AV日韩AV永久无码久久| 国产精品久久久福利| 久久免费香蕉视频| 久久无码人妻一区二区三区 | 久久综合久久综合久久| 亚洲精品无码久久毛片| 国产精品99久久精品| 久久午夜免费视频| 国产福利电影一区二区三区久久久久成人精品综合 | 久久天天躁狠狠躁夜夜2020 | 亚洲精品tv久久久久久久久久| 久久久久久亚洲精品成人| 久久人人爽人人精品视频| MM131亚洲国产美女久久| 2021久久精品免费观看| 欧美精品福利视频一区二区三区久久久精品| 久久久久久午夜成人影院| 中文国产成人精品久久不卡| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 久久最新精品国产| 久久被窝电影亚洲爽爽爽| 亚洲午夜久久久久久久久久| 久久亚洲AV无码精品色午夜麻豆| 国产ww久久久久久久久久| 91久久九九无码成人网站| 久久精品草草草| 久久国产精品99久久久久久老狼| 久久香蕉超碰97国产精品| 久久久国产乱子伦精品作者| 久久人人爽人人爽人人片av高请| 国内高清久久久久久| 亚洲国产精品无码成人片久久| 伊人久久精品无码二区麻豆| 亚洲精品乱码久久久久久久久久久久 |