Trie Tree (前綴樹或字典樹）

可大概先行參考：https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/06.09.md

步驟一：建樹（相同前綴字有共同祖先節點，根節點為空，其餘每個節點的字母不會相同）

步驟二：插入（在插入的同時就須先行統計共同使用此前綴字串的單詞數量）

步驟三：查詢（利用建好的數做查詢）

題目來源：http://hihocoder.com/contest/hiho2/problem/1

1  #include <stdio.h>

2  #include <stdlib.h>

3  #include <iostream>

4  #include <string.h>

5 

6  using namespace std;

7  int le=0;

8  struct node

9  {

10      int next[26];

11      int cnt=0;

12      void init()

13      {

14          cnt=0;

15          memset(next,-1,sizeof(next));

16      }

17  }T[1000000];

18  void insert_(char *s)

19  {

20      int p=0,i=0;

21      while(s[i])

22      {

23          int x=s[i]-'a';

24          if(T[p].next[x]==-1)　若此前綴尚未出現過

25          {

26              T[le].init();

27              T[p].next[x]=le++;

28          }

29          p=T[p].next[x];　走訪

30          T[p].cnt++;　走訪時順便統計出現次數

31          i++;

32      }

33  }

34  void query(char *s)

35  {

36      int i=0,p=0;

37      while(s[i])

38      {

39          int x=s[i]-'a';

40 

41          if(T[p].next[x]==-1)

42          {

43              printf("0\n");

44              return;

45          }

46          p=T[p].next[x];

47          i++;

48      }

49      cout << T[p].cnt << endl;

50 

51  }

52  int main()

53  {

54      int n;

55      cin >> n;

56      le=1;　//節點編號

57      T[0].init();

58      while(n--)

59      {

60          char str[15]="";

61          cin >> str;

62          insert_(str);

63      }

64      int q;

65      cin >> q;

66      while(q--)

67      {

68          char que[15]="";

69          cin >> que;

70          query(que);

71      }

72      return 0;

73  }

進一步學習：http://pisces.ck.tp.edu.tw/~peng/index.php?action=showfile&file=f743c2923f8170798f62a585257fdd8436cd73b6d