题目来自《算法竞赛设计指南》
Tire树是一种可以快速查找字符串的数据结构
模板
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1123;
int tire[MAXN][26], tot = 1;
bool end[MAXN];void add(char* str)
{int len = strlen(str), p = 1; REP(i, 0, len){int ch = str[i] - 'a'; //这里是a不是0if(!tire[p][ch]) tire[p][ch] = ++tot;p = tire[p][ch];}end[p] = true;
}bool search(char* str)
{int len = strlen(str), p = 1;REP(i, 0, len)if(!(p = tire[p][str[i] - 'a']))return false;return end[p];
}int main()
{int n, m;scanf("%d%d", &n, &m);REP(i, 0, n){char s[15];scanf("%s", s);add(s);}while(m--){char s[15];scanf("%s", s);printf("%s\n", search(s) ? "Yes": "No");}return 0;
}
例题.前缀统计
问题： 给n个字符串和m次询问，每次询问给定一个串T，输出有多少个字符串是T的前缀
解答：加入每个字符串的时候在结尾节点加1， 给T后在Tire树上搜一遍，加上沿途字符串结尾的值即可。注意可能有重复的字符串。
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1123;
int tire[MAXN][26], tot = 1;
int end[MAXN]; //避免重复字符串 void add(char* str)
{int p = 1;REP(i, 0, strlen(str)){int ch = str[i] - 'a';if(!tire[p][ch]) tire[p][ch] = ++tot;p = tire[p][ch]; } end[p]++;
} int search(char* str)
{int p = 1, res = 0;REP(i, 0, strlen(str)){if(!(p = tire[p][str[i] - 'a'])) break;res += end[p];}return res;
}int main()
{int n, m;scanf("%d%d", &n, &m);REP(i, 0, n){char s[15];scanf("%s", s);add(s);}while(m--){char s[15];scanf("%s", s);printf("%d\n", search(s));}return 0;
}hdu 1251
和上一题类似，只不过反过来而已
问题： 给n个字符串和m次询问，每次询问给定一个串T，输出T是多少字符串的前缀
解答：可以dfs一遍处理出来每个节点的子树中（包括节点本身）下有多少个字符终点
然后搜到T的最后一个字符，输出预处理的结果即可
注意这道题的输入比较麻烦，判断*s是否为空
#include<cstdio>
#include<algorithm>
#include<cstring>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e6;
int tire[MAXN][26], d[MAXN], tot = 1;
bool End[MAXN];void add(char* str)
{int p = 1;REP(i, 0, strlen(str)){int ch = str[i] - 'a';if(!tire[p][ch]) tire[p][ch] = ++tot;p = tire[p][ch];} End[p] = true;
} int dfs(int p)
{if(End[p]) d[p]++;REP(ch, 0, 26){if(tire[p][ch])d[p] += dfs(tire[p][ch]);}return d[p];
}int search(char* str)
{int p = 1, res = 0;REP(i, 0, strlen(str))if(!(p = tire[p][str[i] - 'a'])) return 0;return d[p];
}int main()
{char s[15];while(gets(s) && *s) add(s);dfs(1);while(~scanf("%s", s)) printf("%d\n", search(s));return 0;
}
【例题】 The XOR Largest Pair
问题：给n个整数A1, A2……An，选出两个数进行异或，得到的结果最大是多少？N <= 1e5, 0 <= Ai < 2^31
解答：我一开始的是把每个数字用二进制的形式表示，然后可以建一颗字典树。然后公共部分肯定异或的值为1.
然后就找最深的结点的数作为第一个数……然后发现找另外一个数就很麻烦了。
看了题解发现要倒着存，也就是从第31位，到第30位……然后每次加入一个数遍历字典树，每次尽量找与当前位不同的数字，这样可以保证最终的结果最大。顺着存就很麻烦。
最后把每个数算出的结果取max即可
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 4e6;
int tire[MAXN][2], tot = 1;void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void add(int x)
{int p = 1;for(int i = 30; i >= 0; i--) {int now = (x >> i) & 1;if(!tire[p][now]) tire[p][now] = ++tot;p = tire[p][now];}
}int search(int x)
{int p = 1, res = 0;for(int i = 30; i >= 0; i--){int now = (x >> i) & 1;if(tire[p][now ^ 1]){p = tire[p][now ^ 1];res |= (1 << i);} else p = tire[p][now]; //}return res;
}int main()
{int n; read(n);int ans = 0;REP(i, 0, n){int x; read(x);add(x);ans = max(ans, search(x));}printf("%d\n", ans);return 0;
}poj 3764
一开始感觉求路径很麻烦，就不知道怎么做
看了题解发现，原来可以用lca的思想来做，lca之前的部分异或起来都是0.所以x到根的值 ^ y到根的值 = x到y的值
那么我们可以预处理每个节点到根的值，那么就转化成上一道题了。
然后这道题丧心病狂的卡常！！我用vector存边，然后就被卡了……第一次用vector被卡……
所以我还是无奈去学了邻接表，过了，0.5S。然后闲着无聊看看读优的效果，去掉读优后直接飙到0.94S
读优大发好！
然后注意一些细节就好了。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cctype>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
const int MAXM = 4e6;
int tire[MAXM][2], n, tot, num;
int d[MAXN], head[MAXN];
struct edge { int to, w, next; };
edge e[MAXN << 1]; //双向边乘以2 void addedge(int from, int to, int w)
{e[tot] = edge{to, w, head[from]};head[from] = tot++;
}void read(int& x)
{int f = 1; x = 0; char ch = getchar();while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }while(isdigit(ch)) { x = x * 10 + ch - '0'; ch = getchar(); }x *= f;
}void dfs(int u, int fa)
{for(int i = head[u]; ~i; i = e[i].next){int v = e[i].to, w = e[i].w;if(v == fa) continue;d[v] = d[u] ^ w;dfs(v, u);}
}void add(int x)
{int p = 1;for(int i = 30; i >= 0; i--) {int now = (x >> i) & 1;if(!tire[p][now]) tire[p][now] = ++num;p = tire[p][now];}
}int search(int x)
{int p = 1, res = 0;for(int i = 30; i >= 0; i--) //0到2^31-1即从第30位到第0位 {int now = (x >> i) & 1;if(tire[p][now ^ 1]){p = tire[p][now ^ 1];res |= (1 << i);} else p = tire[p][now]; }return res;
}int main()
{while(~scanf("%d", &n)){memset(tire, 0, sizeof(tire));memset(head, -1, sizeof(head));num = 1; tot = 0; //注意这里要清零，不只是是数组要清 REP(i, 1, n){int u, v, w;read(u); read(v); read(w);addedge(u, v, w);addedge(v, u, w);}dfs(0, -1);int ans = 0;REP(i, 0, n){ans = max(ans, search(d[i]));add(d[i]);}printf("%d\n", ans);}return 0;
}
poj 3630
以这个很裸的一道题作为结尾
输入一堆字符串，判断有没有字符串是另外一个的前缀。
有两种情况是
（1）加入的时候没有创造新的节点，那么这个字符串就是其他字符串的前缀
（2）如果加入的时候遇到了字符终点，那么就有字符串是当前串的前缀
#include<cstdio>
#include<cctype>
#include<cstring>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e4 + 10;
int tire[MAXN * 10][15], end[MAXN * 10], tot = 1;bool add(char* s)
{int p = 1; bool ok = false;REP(i, 0, strlen(s)){if(end[p]) return false;int ch = s[i] - '0';if(!tire[p][ch]) tire[p][ch] = ++tot, ok = true;p = tire[p][ch]; } end[p] = 1;return ok;
}int main()
{int T, n;scanf("%d", &T);while(T--){scanf("%d", &n);bool ans = true;tot = 1;memset(tire, 0, sizeof(tire));memset(end, 0, sizeof(end));REP(i, 0, n){char s[15];scanf("%s", s);if(!add(s)) ans = false;}printf("%s\n", ans ? "YES" : "NO");}return 0;
}