Trie树

$Trie$树

　　如何快速查找一个单词在字典中是否出现过？kmp；

　　如何快速查找多个单词在字典中是否出现过？Trie树；

　　Trie树是一种非常神奇的数据结构。从百度上偷张图：

　　从一个点走出去到另一个点的路径上的字符连接起来就成了一个字符串，可以在节点上保存一些信息。

　　建立Trie树是非常简单的，就是从根开始，如果有现成的节点就走到那里，如果没有就新建一个走过去。查找其实是一样的，走到字符串的末尾时看看其他字符串有没有在这里结尾的即可。

　　Trie树板子确实简单，但是有一些很巧妙的应用：

　　Phone List：http://poj.org/problem?id=3630

　　题意概述：给定一些数字串，查看里面是否有串是另一个串的前缀。($n<=10000$)

　　把数字串一个个插入Trie树里边，如果一个串在插入过程中没有新建任何节点，说明它是之前插入的某个串的前缀，如果它在插入过程中遇到了某个字符串的结束标记，说明那个字符串是它的前缀。看起来虽然简单，但是刚学Trie树时也不大好想。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=100009;
 8 int n,t,cnt=1;
 9 char s[15];
10 bool f;
11 struct trie
12 {
13     int ch[maxn][10];
14     bool vis[maxn];
15     void clear()
16     {
17         memset(vis,0,sizeof(vis));
18         memset(ch,0,sizeof(ch));
19     }
20     
21     void insert (char *s)
22     {
23         int len=strlen(s);
24         int x=1;
25         int bf=cnt;
26         for (int i=0;i<len;++i)
27         {
28             int c=s[i]-'0';
29             if(!ch[x][c])
30                 ch[x][c]=++cnt;
31             x=ch[x][c];
32             if(vis[x]) f=true;
33         }
34         vis[x]=true;
35         if(bf==cnt) f=true;
36     }
37 }p;
38 
39 int main()
40 {
41     scanf("%d",&t);
42     while (t--)
43     {
44         scanf("%d",&n);
45         f=false;
46         cnt=1;
47         p.clear();
48         for (int i=1;i<=n;++i)
49         {
50             scanf("%s",s);
51             p.insert(s);
52         }
53         if(f)
54             printf("NO
");
55         else
56             printf("YES
");
57     }
58     return 0;
59 }

Phone List

　　The Xor Largest Pair：https://loj.ac/problem/10050

　　题意概述：给定n个数，求从其中选出两个数进行异或的最大值。($n<=10^5$)

　　贪心。首先把每个数都转成二进制并统一位数，如果可以走与这一位不同的路就走，使得异或值尽量大。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=100009*32;
 8 int n,x,ans;
 9 int a[35],cnt=1;
10 struct Trie
11 {
12     int ch[maxn][2];
13     bool vis[maxn];
14     void clear()
15     {
16         memset(ch,0,sizeof(ch));
17         memset(vis,0,sizeof(vis));
18     }
19     void insert()
20     {
21         int x=1;
22         for (int i=1;i<=32;++i)
23         {
24             if(!ch[x][ a[i] ])
25                 ch[x][ a[i] ]=++cnt;
26             x=ch[x][ a[i] ];
27         }
28         vis[x]=true;
29     }
30     int Find()
31     {
32         int ans=0,x=1;
33         for (int i=1;i<=32;++i)
34         {
35             if(ch[x][ a[i]^1 ])
36             {
37                 ans=ans*2+1;
38                 x=ch[x][ a[i]^1 ];
39             }
40             else
41                 x=ch[x][ a[i] ],ans*=2;
42         }
43         return ans;
44     }
45 }p;
46 void spilt (int x)
47 {
48     for (int j=32;j>=1;--j)
49     {
50         a[j]=x%2;
51         x/=2;
52     }
53 }
54 
55 int main()
56 {
57     scanf("%d",&n);
58     p.clear();
59     for (int i=1;i<=n;++i)
60     {
61         scanf("%d",&x);
62         spilt(x);
63         if(i>1) ans=max(ans,p.Find());
64         p.insert();
65     }
66     printf("%d",ans);
67     return 0;
68 }

The Xor Largest Pair

　　Codechef REBXOR：https://www.lydsy.com/JudgeOnline/problem.php?id=4260

　　题意概述：

　　$2≤N≤4*10^5，0≤A_i≤10^9$

　　非常有意思的一道题，求的是两段最大异或和，考虑像两段最大子段和那样枚举断点，用$l_i$表示前$i$个数中的最大单段异或和，$r_i$表示后$i$个数中的最大单段异或和，然后枚举断点统计答案。注意：区间异或和是可以用前缀和思想维护的。其实有点麻烦哎。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=4*100005;
 8 const int len=32;
 9 int n,cnt=1,now;
10 long long ans=0;
11 int a[maxn],l[maxn],r[maxn];
12 int c[34];
13 
14 void spilt (int x)
15 {
16     int s=x;
17     for (int i=len;i>=1;--i)
18     {
19         c[i]=s%2;
20         s/=2;
21     }
22 }
23 
24 struct Trie
25 {
26     int ch[maxn*32][2];
27     bool vis[maxn*32];
28     void clear()
29     {
30         cnt=1;
31         memset(ch,0,sizeof(ch));
32         memset(vis,0,sizeof(vis));
33     }
34     void insert (int now)
35     {
36         spilt(now);
37         int x=1;
38         for (int i=1;i<=len;++i)
39         {
40             if(!ch[x][ c[i] ])
41                 ch[x][ c[i] ]=++cnt;
42             x=ch[x][ c[i] ];
43         }
44         vis[x]=true;
45     }
46     int Find()
47     {
48         int x=1,ans=0;
49         for (int i=1;i<=len;++i)
50         {
51             if(ch[x][ c[i]^1 ])
52                 x=ch[x][ c[i]^1 ],ans=ans*2+1;
53             else
54                 x=ch[x][ c[i] ],ans=ans*2;
55         }
56         return ans;
57     }
58 }p;
59 
60 int main()
61 {
62     scanf("%d",&n);
63     for (int i=1;i<=n;++i)
64         scanf("%d",&a[i]);
65     p.clear();
66     p.insert(0);
67     for (int i=1;i<=n;++i)
68     {
69         now^=a[i];
70         p.insert(now);
71         l[i]=max(l[i-1],p.Find());
72     }
73     p.clear();
74     p.insert(0);
75     now=0;
76     for (int i=n;i>=1;--i)
77     {
78         now^=a[i];
79         p.insert(now);
80         r[i]=max(r[i+1],p.Find());
81     }
82     for (int i=1;i<n;++i)
83         ans=max(ans,(long long)l[i]+r[i+1]);
84     printf("%lld",ans);
85     return 0;
86 }

Codechef REBXOR

　　The xor-longest Path：https://www.lydsy.com/JudgeOnline/problem.php?id=1954

　　题意概述：给定一棵$n$个点的带权树，求树上最长的异或和路径。(异或和路径是什么？反正原题就是这么说的，感觉一下吧。$1<=n<=100000$

　　这道题看起来像是两道题拼起来的题目

　　·https://www.luogu.org/problemnew/show/P2420的思路；

　　·https://loj.ac/problem/10050的实现方法。

　　对于正好做过这两道题目的人来说，这道题就非常简单啦，直接贴代码。

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # define R register int
  5 
  6 using namespace std;
  7 
  8 const int maxn=100009;
  9 const int len=32;
 10 int n,h,x,y,z,cnt=1,ans;
 11 int c[34],a[maxn],dep[maxn],firs[maxn];
 12 struct edge
 13 {
 14     int too,nex,co;
 15 }g[maxn<<1];
 16 
 17 inline char gc()
 18 {
 19     static char buff[1000000],*S=buff,*T=buff;
 20     return S==T&&(T=(S=buff)+fread(buff,1,1000000,stdin),S==T)?EOF:*S++;
 21 }
 22 
 23 int read()
 24 {
 25     int x=0;
 26     char c=gc();
 27     while (!isdigit(c))
 28         c=gc();
 29     while (isdigit(c))
 30     {
 31         x=(x<<3)+(x<<1)+(c^48);
 32         c=gc();
 33     }
 34     return x;
 35 }
 36 
 37 void spilt (int x)
 38 {
 39     int no=a[x];
 40     for (R i=len;i>=1;--i)
 41     {
 42         c[i]=no%2;
 43         no/=2;
 44     }
 45 }
 46 
 47 struct Trie
 48 {
 49     int ch[maxn*32][2];
 50     bool vis[maxn*32];
 51     void clear()
 52     {
 53         memset(ch,0,sizeof(ch));
 54         memset(vis,0,sizeof(vis));
 55     }
 56     void insert()
 57     {
 58         int x=1;
 59         for (R i=1;i<=len;++i)
 60         {
 61             if(!ch[x][ c[i] ])
 62                 ch[x][ c[i] ]=++cnt;
 63             x=ch[x][ c[i] ];
 64         }
 65         vis[x]=true;
 66     }
 67     int Find()
 68     {
 69         int x=1,ans=0;
 70         for (R i=1;i<=len;++i)
 71         {
 72             if(ch[x][ c[i]^1 ])
 73             {
 74                 ans=ans*2+1;
 75                 x=ch[x][ c[i]^1 ];
 76             }
 77             else
 78             {
 79                 ans=ans*2;
 80                 x=ch[x][ c[i] ];
 81             }
 82         }
 83         return ans;
 84     }
 85 }p;
 86 
 87 void dfs (int x)
 88 {
 89     int j;
 90     for (R i=firs[x];i;i=g[i].nex)
 91     {
 92         j=g[i].too;
 93         if(dep[j]) continue;
 94         dep[j]=dep[x]+1;
 95         a[j]=a[x]^g[i].co;
 96         dfs(j);    
 97     }
 98 }
 99 
100 void add (int x,int y,int co)
101 {
102     g[++h].too=y;
103     g[h].nex=firs[x];
104     firs[x]=h;
105     g[h].co=co;
106 }
107 
108 int main()
109 {
110     scanf("%d",&n);
111     for (R i=1;i<n;++i)
112     {
113         x=read(),y=read(),z=read();
114         add(x,y,z);
115         add(y,x,z);
116     }
117     dep[1]=1;
118     dfs(1);
119     p.clear();
120     for (R i=1;i<=n;++i)
121     {
122         spilt(i);
123         ans=max(ans,p.Find());
124         p.insert();
125     }
126     printf("%d",ans);
127     return 0;
128 }

The Xor-longest Path

　　[Usaco2008 Dec]Secret Message 秘密信息：https://www.lydsy.com/JudgeOnline/problem.php?id=1590

　　题意概述：给出$n$个信息串和$m$个密码串，求对于每一个密码串，有多少个信息串是它的前缀或者它是那个信息串的前缀。$n,m<=50000$

　　看起来挺复杂的，其实可以分开考虑。

　　·有多少个信息串是它的前缀：记录每个节点结束的信息串数量，沿着匹配的路径全部加起来。

　　·是多少个信息串的前缀：当匹配结束时，记录它下面的结束指针数量。

　　实现的时候可以一起统计。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=500009;
 8 int n,m,cnt=1,len;
 9 int c[10009];
10 struct Trie
11 {
12     int ch[maxn][2];
13     int en[maxn];
14     int s[maxn];
15     void clear()
16     {
17         memset(ch,0,sizeof(ch));
18         memset(en,0,sizeof(en));
19         memset(s,0,sizeof(s));
20     }
21     void insert()
22     {
23         int x=1;
24         for (int i=1;i<=len;++i)
25         {
26             if(!ch[x][ c[i] ])
27                 ch[x][ c[i] ]=++cnt;
28             x=ch[x][ c[i] ];
29         }
30         en[x]++;
31     }
32     int ask()
33     {
34         int x=1,ans=0;
35         for (int i=1;i<=len;++i)
36         {
37             if(!ch[x][ c[i] ])
38                 return ans;
39             x=ch[x][ c[i] ];
40             ans+=en[x];
41         }
42         return ans+s[x];
43     }
44 }p;
45 
46 void up (int x)
47 {
48     if(p.ch[x][0])
49     {
50         up(p.ch[x][0]);
51         p.s[x]+=p.s[ p.ch[x][0] ]+p.en[ p.ch[x][0] ];
52     }
53     if(p.ch[x][1])
54     {
55         up(p.ch[x][1]);
56         p.s[x]+=p.s[ p.ch[x][1] ]+p.en[ p.ch[x][1] ];
57     }
58 }
59 
60 int main()
61 {
62     scanf("%d%d",&n,&m);
63     p.clear();
64     for (int i=1;i<=n;++i)
65     {
66         scanf("%d",&len);
67         for (int i=1;i<=len;++i)
68             scanf("%d",&c[i]);
69         p.insert();
70     }
71     up(1);
72     for (int i=1;i<=m;++i)
73     {
74         scanf("%d",&len);
75         for (int i=1;i<=len;++i)
76             scanf("%d",&c[i]);
77         printf("%d
",p.ask());
78     }
79     return 0;
80 }

Secret Message

　　[HNOI2004]L语言:https://www.lydsy.com/JudgeOnline/problem.php?id=1212

　　题意概述：给出一个字典，一篇没有标点的文章，问最多能读懂到哪里。$1<=n<=20$，每个单词长度不超过$10$，文章长度不超过$1M$。

　　乍一看真是一道很妙的题目，略微思索发现好像又是一个枚举断点的套路题。dp[i]表示$1-i$这一段文章是否可以看懂，因为单词长度比较短，所以每次只从前边的10个进行转移即可，不过这样就体现不了Trie树的优势了，可以用刷表法，边走边统计，复杂度$O(10*len_M)$

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 
 5 using namespace std;
 6 
 7 const int maxn=(1<<20)+10;
 8 int n,m,las=0,cnt=1;
 9 bool f[maxn];
10 char c[maxn];
11 struct edge
12 {
13     int ch[200][26];
14     bool vis[200];
15     void clear()
16     {
17         memset(ch,0,sizeof(ch));
18         memset(vis,0,sizeof(vis));
19     }
20     void insert()
21     {
22         int x=1,n;
23         int len=strlen(c+1);
24         for (int i=1;i<=len;++i)
25         {
26             n=c[i]-'a';
27             if(!ch[x][n]) ch[x][n]=++cnt;
28             x=ch[x][n];
29         }
30         vis[x]=true;
31     }
32     void find (int beg)
33     {
34         int x=1,n;
35         while (1)
36         {
37             n=c[beg]-'a';
38             if(!ch[x][n]) break;
39             x=ch[x][n];
40             if(vis[x]) f[beg]=true;
41             beg++; 
42         }
43     }
44 }p;
45 
46 int main()
47 {
48     scanf("%d%d",&n,&m);
49     p.clear();
50     for (int i=1;i<=n;++i)
51     {
52         scanf("%s",c+1);
53         p.insert();
54     }
55     for (int i=1;i<=m;++i)
56     {
57         memset(f,0,sizeof(f));
58         scanf("%s",c+1);
59         int len=strlen(c+1);
60         f[0]=true;
61         las=0;
62         for (int i=0;i<=len;++i)
63         {
64             if(!f[i]) continue;
65             las=i;
66             if(i!=len) p.find(i+1);
67         }
68         printf("%d
",las);
69     }
70     return 0;
71 }

L语言

　　[Scoi2016]背单词：https://www.lydsy.com/JudgeOnline/problem.php?id=4567

　　题意概述：题目描述很绕，根本看不懂，从网上抄了一段比较正常的翻译：

　　在此感谢f321dd的正常翻译。

　　Trie树能处理后缀吗？反过来就可以......把字符串反过来建树，首先我们可以发现第一种情况是不可能发生的，因为n*n实在太大了，所以进行一些修补一定是更优的。因为空串是任意串的后缀，所以第二种情况和第三种也可以合并到一起去，现在问题就变成了，求一棵树的一个拓扑序，使得每个点的编号与它父亲的编号差的和最小。

　　(手玩发现)每次先访问子树大小最小的子树是最优的，至于为什么，就不是很清楚了。

  1 # include <cstdio>
  2 # include <iostream>
  3 # include <cstring>
  4 # include <string>
  5 # include <queue>
  6 # define R register int
  7 
  8 using namespace std;
  9 
 10 const int maxl=510005;
 11 int n,cnt=1;
 12 char s[maxl];
 13 int h,dep[maxl],tim=0,ch[maxl][26],firs[maxl],siz[maxl];
 14 typedef pair <int,int> pii;
 15 long long ans=0;
 16 bool vis[maxl];
 17 struct edge
 18 {
 19     int too,nex;
 20 }g[maxl<<1];
 21 
 22 void add (int x,int y)
 23 {
 24     g[++h].too=y;
 25     g[h].nex=firs[x];
 26     firs[x]=h;
 27 }
 28 
 29 void insert()
 30 {
 31     int len=strlen(s+1),x=1,n;
 32     for (R i=1;i<=len/2;++i)
 33         swap(s[i],s[len-i+1]);
 34     for (R i=1;i<=len;++i)
 35     {
 36         n=s[i]-'a';
 37         if(!ch[x][n]) ch[x][n]=++cnt;
 38         x=ch[x][n];
 39     }
 40     vis[x]=true;
 41 }
 42 
 43 void build (int x,int roo)
 44 {
 45     int n;
 46     for (int i=0;i<26;++i)
 47     {
 48         n=ch[x][i];
 49         if(!n) continue;
 50         if(vis[n])
 51         {
 52             add(roo,n);
 53             build(n,n);
 54         }
 55         else build(n,roo);
 56     }
 57 }
 58 
 59 void dfs (int x)
 60 {
 61     siz[x]=1;
 62     for (R i=firs[x];i;i=g[i].nex)
 63     {
 64         dfs(g[i].too);
 65         siz[x]+=siz[ g[i].too ];
 66     }
 67 }
 68 
 69 void dp (int x)
 70 {
 71     priority_queue <pii,vector<pii>,greater<pii> > q;
 72     while (q.size()) q.pop();
 73     for (int i=firs[x];i;i=g[i].nex)
 74         q.push(make_pair(siz[ g[i].too ],g[i].too));
 75     int j;
 76     while (q.size())
 77     {
 78         j=q.top().second;
 79         dep[j]=++tim;
 80         dp(j);
 81         q.pop();
 82     }
 83 }
 84 
 85 void coun (int x)
 86 {
 87     int j;
 88     for (int i=firs[x];i;i=g[i].nex)
 89     {
 90         j=g[i].too;
 91         ans+=dep[j]-dep[x];
 92         coun(j);
 93     }
 94 }
 95 
 96 int main()
 97 {
 98     scanf("%d",&n);
 99     for (int i=1;i<=n;++i)
100     {
101         scanf("%s",s+1);
102         insert();    
103     }
104     build(1,1);
105     dfs(1);
106     dp(1);
107     coun(1);
108     printf("%lld",ans);
109     return 0;
110 }

背单词

　　[JSOI]Word Query电子字典：https://www.lydsy.com/JudgeOnline/problem.php?id=1819

　　题意概述：给定n个单词和m个查询串，求对于每一个查询串，可以通过一步修改变成多少个单词。一步修改：插入一个字符删除一个字符修改一个字符。$N<=10,000 ; M<=10,000 ; len<=20$

　　看起来挺有意思...其实非常暴力，就是模拟每一种修改：

　　·插入：在Trie树上向下随便跳一步；

　　·删除：从pos+1开始匹配；

　　·修改：pos+1的同时在Trie树上向下随便跳一步；

　　注意判重，我的方法很简单，就是把每次统计到的答案在vis中减去，每做完一个串再复原，这还是跟“列队”一题学的，非常巧妙。有一些小细节：第一个字符不好处理，可以统一在前边多加一个字符；最后一个字符后边也可以再插入，建议特判。

 1 # include <cstdio>
 2 # include <iostream>
 3 # include <cstring>
 4 # include <string>
 5 # include <vector>
 6 # define R register int
 7 
 8 using namespace std;
 9 
10 const int maxn=200005;
11 int n,m,cnt=1,ans;
12 bool f;
13 vector <int> v;
14 char s[25];
15 int ch[maxn][26];
16 int vis[maxn];
17 
18 void insert()
19 {
20     int len=strlen(s+1),x=1,n;
21     for (R i=0;i<=len;++i)
22     {
23         n=s[i]-'a';
24         if(!ch[x][n]) ch[x][n]=++cnt;
25         x=ch[x][n];
26     }
27     vis[x]++;
28 }
29 
30 void find (int pos,int x,int len,int c)
31 {
32     int n=s[pos]-'a';
33     if(pos==len+1&&c==0&&vis[x])
34     {
35         f=true;
36         return ;
37     }
38     if(pos==len+1&&c==1)
39     {
40         ans+=vis[x];
41         if(vis[x]) v.push_back(x);
42         vis[x]=0;
43         return ;
44     }
45     if(pos==len+1) 
46     {
47         if(c) return ;
48         for (R i=0;i<26;++i)
49         {
50             if(ch[x][i])
51             {
52                 ans+=vis[ ch[x][i] ];
53                 if(vis[ ch[x][i] ]) v.push_back( ch[x][i] );
54                 vis[ ch[x][i] ]=0;
55             }
56         }
57         return ;
58     }
59     if(ch[x][n]) find(pos+1,ch[x][n],len,c);
60     if(c) return ;
61     find(pos+1,x,len,1);
62     for (R i=0;i<26;++i)
63         if(ch[x][i]) find(pos,ch[x][i],len,1),find(pos+1,ch[x][i],len,1);
64 }
65 
66 int main()
67 {
68     scanf("%d%d",&n,&m);
69     for (R i=1;i<=n;++i)
70     {
71         scanf("%s",s+1);
72         s[0]='a';
73         insert();
74     }
75     v.clear();
76     for (R i=1;i<=m;++i)
77     {
78         ans=0;
79         f=false;
80         scanf("%s",s+1);
81         s[0]='a';
82         int len=strlen(s+1);
83         find(0,1,len,0);
84         if(f)
85             printf("-1
");
86         else
87             printf("%d
",ans);
88         int siz=v.size();
89         for (R j=0;j<siz;++j)
90             vis[ v[j] ]=1;
91         v.clear();
92     }
93     return 0;
94 }

电子词典

---shzr