trie树？？？

　　trie树是一种树形结构，可以用来找前缀固定的字符串。

思想

　　其实思想很简单，就是将每个字符串都挂到树上去，如果当前节点在之前已经有了就不用新建节点，可以继续前面的向下找。否则就新建一个节点，这样就节省了时间和空间。

具体实现

　　代码一看就懂了，不多bb

板子题

　　codevs4189

 

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=400010,L=12;
int tree[N][27],tot,m;
char s[L];
void add(char S[])
{
    int now=0;
    int l=strlen(S);
    for(int i=0;i<l;++i)
    {
        
        int x=S[i]-'a';
        if(tree[now][x]) now=tree[now][x];
        else 
        {
            tree[now][x]=++tot;
             now=tot;
        }
    }
     return;
}
bool find(char S[])
{
    int l=strlen(S),now=0;
    for(int i=0;i<l;++i)
    {
        int x=S[i]-'a';
        if(tree[now][x]) now=tree[now][x];
        else return 0;
    }
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s);
        add(s);
    }
    scanf("%d",&m);
    while(m--)
    {
        scanf("%s",s);
        if(find(s)) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
codevs4189

01trie树

　　01trie树是一种特殊的trie树，它是将整数按照二进制挂到了树上，这样有时候更加有利于处理问题。比如处理异或值问题。

例题：

　　csu1216

代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cstring>
 4 using namespace std;
 5 const int N=100010;
 6 int n;
 7 int tree[N*32][2];
 8 int a[N],val[N*32];
 9 int tot;
10 void add(int x) {
11     int now=0;
12     for(int i=31; i>=0; --i) {
13         int c=x>>i&1;
14         if(!tree[now][c])
15             tree[now][c]=++tot;
16         now=tree[now][c];
17     }
18     val[now]=x;
19 }
20 int query(int x) {
21     int now=0;
22     for(int i=31; i>=0; --i) {
23         int c=x>>i&1;
24         if(tree[now][c^1]) {
25             now=tree[now][c^1];
26         } else now=tree[now][c];
27     }
28     return val[now];
29 }
30 void pre()
31 {
32     memset(tree,0,sizeof(tree));
33     tot=0;
34 }
35 int main() {
36     while(scanf("%d",&n)==1) {
37         pre();
38         int maxx=0;
39         for(int i=1; i<=n; ++i) {
40             scanf("%d",&a[i]);
41             add(a[i]);
42         }
43         int ans=0;
44         for(int i=1; i<=n; ++i) {
45             int kk=query(a[i]);
46             ans=max(ans,kk^a[i]);
47         }
48         printf("%d\n",ans);
49     }
50 
51     return 0;
52 }
csu1216