静态字典树

　　动态字典树每次都要new一个内存来操作，所以耗时也是较多的；所以我们可以先一次性开辟出足够的空间，然后模拟动态字典树的创建查找过程来写出相应的静态字典树。

代码都差不多，主要是你得先学会了动态字典树；接下来的事情就是模拟了，，，模拟，，模拟。

结构定义：

struct Trie
{
    int next[26];
    int cnt;           // 根据需要灵活变动
    void Init()
    {
        cnt = 0;
        _clr(next, 0);
    }
}trie[N];
int size;   // 节点标知

字典树创建：

 1 void Insert(char *s)
 2 {
 3     int Pre = 0;
 4     for(int i=0; s[i]; i++)
 5     {
 6         int id = s[i] - 'a';
 7         if(trie[Pre].next[id]==0)
 8         {
 9             trie[Pre].next[id] = ++ size;  // 节点不存在开辟新节点
10             Pre = size;         // 继续向下查找
11             /*
12              *  根据需要添加
13             */
14             trie[Pre].cnt++;    // 根据需要添加
15         }
16         else
17         {
18             Pre = trie[Pre].next[id]; // 向下传递
19              /*
20              *  根据需要添加
21             */
22             trie[Pre].cnt++;
23         }
24     }
25}

查找：

 1 int Find(char *s)
 2 {
 3     int Pre = 0;
 4     for(int i=0; s[i]; i++)
 5     {
 6         int id = s[i] - 'a';
 7         if(trie[Pre].next[id]==0)
 8             return 0;
 9         Pre = trie[Pre].next[id];
10     }
11     return trie[Pre].cnt;
12 }

以poj 3630为例：http://poj.org/problem?id=3630

 1 #include <cstdio>
 2 #include <cstring>
 3 #define _clr(x, y) memset(x, y, sizeof(x))
 4 #define N 100005
 5 using namespace std;
 6 struct Trie
 7 {
 8     int next[10];
 9     int suffix;
10     void init()
11     {
12         suffix = 0;
13         _clr(next, 0);
14     }
15 }trie[N];
16 int size;
17 
18 void Init()
19 {
20     size = 0;
21     for(int i=0; i<N; i++)
22         trie[i].init();
23 }
24 //  存在前缀返回false
25 bool Insert(char *s)
26 {
27     int Pre = 0;
28     bool tag = true;
29     for(int i=0; s[i]; i++)
30     {
31         int id = s[i] - '0';
32         if(trie[Pre].next[id]==0)
33         {
34             tag = false;
35             trie[Pre].next[id] = ++size;
36             Pre = size;
37         }
38         else
39         {
40             Pre = trie[Pre].next[id];
41             if(trie[Pre].suffix)     // 前面是当前的前缀
42                 return false;
43         }
44     }
45     trie[Pre].suffix = true;
46     return !tag;               //当前是否为前面的前缀
47 }
48 
49 int main()
50 {
51     int T, n;
52     char str[14];
53     scanf("%d", &T);
54     while(T--)
55     {
56         bool tag = true;
57         Init();
58         for(int i=0; i<N; i++)
59             trie[i].init();
60         scanf("%d", &n);
61         while(n--)
62         {
63             scanf("%s", str);
64             if(tag)
65                 tag = Insert(str);
66         }
67         puts(tag ? "YES":"NO");
68     }
69     return 0;
70 }

View Code

相关推荐