HDU 1251 統計難題 （Trie樹——字元串算法）

在vj上拉了一些題，有一題它需要用到trie樹。

題目大意是這樣的：給一個單詞表(隻有小寫字母組成,不會有重複的單詞出現),讓我們統計出以某個字元串為字首的單詞數量(單詞本身也是自己的字首).

Sample Input

banana
band
bee
absolute
acm

ba
b
band
abc
           

Sample Output

2
3
1
0
           

這種字首的問題，在我不知道trie樹的時候，就暴力嘛（暴力出真知/斜眼笑）！每個字元串從單詞表開始到結尾依次判斷，但是時間複雜度就很大了，這個複雜度有O(n^2)，如果n很大，這顯然是不好的。

是以介紹trie算法。

參考一位巨巨的文章：

http://blog.csdn.net/hackbuteer1/article/details/7964147

prie樹：

特征：

（1）根節點設為空，其他的每個節點隻包含一個字元。

（2）從根節點到樹中的某一個節點，路上經過的字元從上到下連接配接起來，為該節點對應的字元串。

舉例：

banana
band
bee
absolute
acm

NULL ->a->b->s->o->l->u->t->e
        ->c->m
     ->b->a->n->a->n->a
              ->d
           

因為沒有找到合适的畫樹圖軟體，就用上面的表示，從NULL開始，同一列的為同一層。

Trie樹結點結構體聲明如下。

typedef struct Trie_node  
{  
    int count;                    // 統計從根節點到此結點的字元串出現的次數  
    struct Trie_node* next[26];   // 指向各個子樹的指針，字母26個  
    bool exist;                   // 标記此結點是否構成單詞
}TrieNode , *Trie;  
           

建立新結點：

用malloc開辟一個位址，将此結點的count置0，子樹置空，構成單詞标記置false。

TrieNode* createTrieNode()
{
    TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
    node->count = ;
    node->exist = false;
    memset(node->next, NULL, sizeof(node->next));
    return node;
}
           

建立單詞表：

這裡就開始了trie樹的build了，注意從根結點開始進行建樹，過程通過字元的id來判斷子樹是否被建立過，如果沒有建立過，就malloc一個子結點，然後到達子節點，依次往下。

舉例：

注意括号中為count數

• 單詞1：banana：

  NULL ->b(1)->a(1)->n(1)->a(1)->n(1)->a(1)  
  此單詞建構完成，最後一個a結點的exit置為true。
             

• 單詞2：band：

  NULL->b(2)->a(2)->n(2)->a(1)->n(1)->a(1)
                        ->d(1)
  此單詞建構完畢，發現結點b,a,n的count數變成了2，并且結點d的exit置為true。
             

  代碼如下：

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 += ;
    }
    node->exist = true;
}
           

查詢：

從NULL開始，取s[i]，依次判斷node->next[s[i]-‘a’]是否為空，如果為空，說明單詞中沒有要查詢的字元串的字元，則傳回0；否則就取最後一個結點的count。

就上面的例子來看，即現在的trie樹為：

NULL->b(2)->a(2)->n(2)->a(1)->n(1)->a(1)
                      ->d(1)
           

我們查詢字元串s為“ba”：

1.先是‘b’：從NULL開始發現下一個結點是b，繼續

2.最後是‘a’：從b開始發現下一個結點是a，則傳回2。

單詞表是banana 和 band ， 查詢的是“ba”，的确是兩個單詞的字首。

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 ;
    }
    return node->count;
}
           

完整代碼如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<malloc.h>
using namespace std;
/*聲明結構體*/
typedef struct Trie_node{
    int count;
    struct Trie_node* next[];
    bool exist;
}TrieNode, *Trie;
/*建立新結點*/
TrieNode* createTrieNode()
{
    TrieNode* node = (TrieNode *)malloc(sizeof(TrieNode));
    node->count = ;
    node->exist = false;
    memset(node->next, NULL, sizeof(node->next));
    return node;
}
/*建trie樹*/
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 += ;
    }
    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 ;
    }
    return node->count;
}

int main()
{
    Trie root = createTrieNode();
    char str[];
    bool flag = false;
    while(gets(str))
    {
        if(flag) printf("%d\n", Trie_search(root, str));
        else{
            if(strlen(str) != )
            {
                Trie_insert(root, str);
            }else{
                flag = true;
            }
        }
    }
    return ;
}