暑期专题二 Trie树 + AC自动机
作为字符串的又一个经典算法，Trie树的核心思想就在于利用好多个字符串的公共前缀来降低查找时间。因此，Trie树是解决各类字符串查找和前缀判定的有力武器。
它的查找时间非常短（常数），但是空间消耗巨大，甚至比map还要略大。
1.NKOJ1931 电话簿
问题描述
何老板的手机很先进，当要拨打一个号码时，你需敲出该号码的前面几个数字，手机就会自动找出以该数字为前缀的所有号码。
比如下列电话薄：
TOM:1388
JIM:13885599999
LEE:13812345678
TEC:0236588888
如果何老板敲了\(138\)三个数字，手机屏幕上就会显示TOM、JIM和LEE的名字。很是方便呀！
但是何老板发现有不好的地方就是比如他想拨打JIM的号码，当他在手机上敲了\(1388\)这四个数字，没等何老板敲完其它数字，手机就会自动拨打TOM的号码，这让何老板很是烦恼。也就是说一旦手机发现你当前敲出的数字与电话薄中的某个号码匹配了，它就会自动拨打该号码。
于是何老板想知道，他的电话薄中，也就是是否存在一个号码是其它号码的前缀的情况。
输入格式
第一行，一个整数\(t\)，表示有\(t\)组测试数据\(1 ≤ t ≤ 40\)
对于每组测试数据：
第一行一个整数\(n（1 ≤ n ≤ 10000）\),表示电话薄中有n个号码
接下来\(n\)行，每行一个数字，表示一个电话号码，每个电话号码的长度不超过10，并且是唯一的。
输出格式
每组测试数据输出一行，如果有有号码是其它号码的前缀，输出"NO"否则输出"YES"
思路：板题，直接利用Trie树的性质判定前缀即可。
#include
using namespace std;
char ch[100005];
int val[100005], tot, Go[100005][10], rt;
inline int node_new()
{
int x = ++tot;
memset(Go[x], 0, sizeof Go[x]);
return x;
}
inline int insert(char *s)
{
int u = rt; bool flg = 1;
for (int i = 0; s[i]; i++)
{
if (!isdigit(s[i])) continue;
int id = s[i] - '0';
if (val[u]) return 1;
if (!Go[u][id]) flg = 0, Go[u][id] = node_new(), val[Go[u][id]] = 0;
u = Go[u][id];
}
val[u] = 1;
return flg;
}
inline void solve()
{
memset(val, 0, sizeof val);
memset(Go, 0, sizeof Go);
tot = 0;
rt = node_new();
int n; bool flg = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%s", ch);
if (!flg && insert(ch)) flg = 1, puts("NO");
} if (!flg) puts("YES");
}
int main()
{
int t;
scanf("%d", &t);
while (t--) solve();
}
2.NKOJ1873 Cow XOR奶牛异或
问题描述
农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有\(N(1 <= N <= 100,000)\)个奶牛在他面前排成一行(按序号\(1..N\)的顺序)，按照它们的社会等级排序。奶牛\(1\)有最高的社会等级，奶牛\(N\)最低。每个奶牛同时被指定了一个不唯一的附加值，这个数在\(0..2^21 - 1\)的范围内。
帮助农民约翰找出应该从哪一头奶牛开始喂，使得从这头奶牛开始的一个连续的子序列上，奶牛的附加值的异或最大。
如果有多个这样的子序列，选择结尾的奶牛社会等级最高的。如果还不唯一，选择最短的。
输入格式
第1行:一个单独的整数N。
第2到N + 1行:N个\(0~2^21 - 1\)之间的整数，代表每头奶牛的被赋予的数。
第j行描述了社会等级j - 1的奶牛。
输出格式
第 1 行: 3个空格隔开的整数，分别为：最大的异或值，序列的起始位置、终止位置。 时限0.5秒
思路：考虑到异或是具有前缀性质的，我们求出这个序列的前缀异或和。然后按位分为21位插入到字典树中。当查找一个数时，尽可能高位不同（显然更优），然后查找最大值即可。
#include
using namespace std;
int val[2000005], a[2000005], pre[2000005], rt, Go[2000005][2], tot;
inline int node_new()
{
int x = ++tot;
memset(Go[x], 0, sizeof Go[x]);
return x;
}
inline void insert(int k)
{
int u = rt;
for (int i = 20; ~i; i--)
{
int id = (pre[k] >> i) & 1;
if (!Go[u][id]) Go[u][id] = node_new();
u = Go[u][id];
} val[u] = k;
}
inline int find(int k)
{
int u = rt;
for (int i = 20; ~i; i--)
{
int id = pre[k] >> i & 1 ^ 1;
if (!Go[u][id]) id ^= 1;
u = Go[u][id];
} return val[u];
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1, x; i <= n; i++) scanf("%d", &x), pre[i] = pre[i - 1] ^ x;
rt = node_new();
insert(1); int ans1 = 1, ans2 = 1, ans = pre[1];
for (int i = 2; i <= n; i++)
{
int t = find(i);
if ((pre[t] ^ pre[i]) > ans) ans = pre[t] ^ pre[i], ans1 = t + 1, ans2 = i;
insert(i);
} printf("%d %d %d\n", ans, ans1, ans2);
}
3.[JSOI2015]字符串树
问题描述
萌萌买了一颗字符串树的种子，春天种下去以后夏天就能长出一棵很大的字符串树。字符串树很奇特，树枝上都密密麻麻写满了字符串，看上去很复杂的样子。
字符串树本质上还是一棵树，即\(N\)个节点\(N-1\)条边的连通无向无环图，节点从\(1\)到\(N\)编号。与普通的树不同的是，树上的每条边都对应了一个字符串。萌萌和JYY在树下玩的时候，萌萌决定考一考JYY。每次萌萌都写出一个字符串\(S\)和两个节点\(U,V\)，需要JYY立即回答\(U\)和\(V\)之间的最短路径（即,之间边数最少的路径。由于给定的是一棵树，这样的路径是唯一的）上有多少个字符串以为前缀。
JYY虽然精通编程，但对字符串处理却不在行。所以他请你帮他解决萌萌的难题。
输入格式
输入第一行包含一个整数\(N\)，代表字符串树的节点数量。
接下来\(N-1\)行，每行先是两个数\(U,V\)，然后是一个字符串\(S\),表示节点和\(U\)节点\(V\)之间有一条直接相连的边，这条边上的字符串是\(S\)。输入数据保证给出的是一棵合法的树。
接下来一行包含一个整数\(Q\)，表示萌萌的问题数。
接来下\(Q\)行，每行先是两个数\(U,V\)，然后是一个字符串\(S\),表示萌萌的一个问题是节点\(U\)和节点\(V\)之间的最短路径上有多少字符串以\(S\)为前缀。
输入中所有字符串只包含\(a-z\)的小写字母。
\(1\leq N,Q \leq 10^5\)，且输入所有字符串长度不超过\(10\)。
输出格式
输出\(Q\)行，每行对应萌萌的一个问题的答案。
思路：可持久化字典树板题。类似主席树，前缀的数量显然是有前缀性质的（即可减性）。所以考虑对于每一个节点都建一棵字典树，记录根到这个节点的字符串。但是显然这样空间会爆炸，所以考虑像主席树一样的做法，在父亲节点的基础上再插入父亲到儿子这条边的字符串，这样的话我们还需要维护lca，那么从\(U\)到\(V\)的前缀我们就转化为了类似lca求距离的形式。
#include
using namespace std;
int n ,m, Go[1000005][30], cnt[1000005], cntid(1), tot, head[100010], rt[100010];
int dep[100005], f[100005][20];
char a[12];
struct edge {
int nxt, to;
char s[12];
}e[200020];
inline void add_e(int u, int v) {e[++tot].to = v; e[tot].nxt = head[u]; head[u] = tot; memcpy(e[tot].s, a, 12);}
inline void modify(int &x, int fa, char *s)
{
x = ++cntid;
int u = x;
for (int i = 0; s[i]; i++)
{
int c = s[i] - 'a';
for (int j = 0; j <= 25; j++) if (j ^ c) Go[u][j] = Go[fa][j];
fa = Go[fa][c];
u = Go[u][c] = ++cntid;
cnt[u] = cnt[fa] + 1;
}
}
inline int lca(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
int d = dep[x] - dep[y];
for (int i = 17; ~i; i--) if ((1 << i) & d) x = f[x][i];
if (x == y) return x;
for (int i = 17; ~i; i--) if (f[x][i] ^ f[y][i]) x = f[x][i], y = f[y][i];
return f[x][0];
}
void dfs(int u, int fa)
{
dep[u] = dep[fa] + 1;
f[u][0] = fa;
for (int i = 1; i <= 17; i++) f[u][i] = f[f[u][i - 1]][i - 1];
for (int i = head[u]; i; i = e[i].nxt) if (e[i].to ^ fa) modify(rt[e[i].to], rt[u], e[i].s), dfs(e[i].to, u);
}
inline int query(int x)
{
int u = rt[x];
for (int i = 0; a[i]; i++)
{
if (!Go[u][a[i] - 'a']) return 0;
u = Go[u][a[i] - 'a'];
} return cnt[u];
}
int main()
{
scanf("%d", &n);
for (int i = 1, x, y; i < n; i++)
{
scanf("%d%d%s", &x, &y, &a[0]);
add_e(x, y), add_e(y, x);
} rt[1] = 1, dfs(1, 0);
scanf("%d", &m);
for (int i = 1, x, y; i <= m; i++)
{
scanf("%d%d%s", &x, &y, &a[0]);
int l = lca(x, y);
printf("%d\n", query(x) + query(y) - query(l) * 2);
}
}
4.NKOJ6645 编码
问题描述
Bob 最新学习了一下二进制前缀编码的那一套理论。二进制编码是指一个由\(n\)个互不相同的二进制串\(s_1,s_2,...,s_n\)构成的集合。而如果一套编码理论满足，对于任意的\(i \not= j\)，\(s_i\)不是\(s_j\)的前缀，那么我们称它为前缀编码。
Bob 发现了一张上面写有\(n\)行二进制编码的纸，但这张纸年代久远，有些字迹已经模糊不清。幸运的是，每一行至多只会有一个模糊的字符。
Bob 想知道这\(n\)行二进制编码是否有可能是一个前缀编码？
输入格式
第一行一个整数 ，表示编码的大小。
接下来 行，每行一个由 0、1 及 ? 组成的字符串。保证每一行至多有一个 ?。
输出格式
如果这\(n\)个二进制编码可能是前缀编码，输出 YES，否则输出 NO。
思路：不同于Trie树的板题，这个题其实还有一些别的东西。首先判断一个字符串是不是另一个字符串的前缀是非常模板的问题，直接套Trie树模板即可。但是我们发现这个题有一个非常坑的地方：'?'的存在！有了这个'?'，前缀就无法确定。
怎么办呢？
发现每一个字符串最多只有一个'?'，我们通过思考可以想到，这个'?'，实际上表达了一个信息：即这个字符为0和为1的状态必须且只能选一个。这让我们想到了2-SAT算法！2-SAT算法即是用来解决这种问题的。那么这个题转化为了一个2-SAT的基础建模题。
1.\(s_i\)为\(s_j\)前缀
这种情况我们就可以将它转化为2-SAT的常见模型————\(i\)和\(j\)最多只能选一个，那么\(i\)向\(j'\)连边，\(j\)向\(i'\)连边。
2.\(s_i\)没有'?'
转化为2-SAT模型中的已选模型————\(i'\)向\(i\)连边。
然后直接跑2-SAT即可。
#include
using namespace std;
char ch[5000005];
int id[5000005][2], cnt, Go[5000005][2], tot;
struct node {
int to, nxt;
}e[10000005]; int head[5000005], tt;
inline void add_e(int u, int v) {e[++tt].to = v; e[tt].nxt = head[u]; head[u] = tt;}
inline void insert(char *s, int k)
{
int u = 0;
for (int i = 0, c; s[i]; i++)
{
if (s[i] == '?') c = k & 1;
else c = s[i] - '0';
if (!Go[u][c]) Go[u][c] = ++tot;
u = Go[u][c];
}
if (!id[u][0]) add_e(k, id[u][0] = ++cnt), add_e(id[u][1] = ++cnt, k ^ 1);
else
{
add_e(k, id[u][1]), add_e(id[u][0], k ^ 1);
add_e(k, ++cnt), add_e(id[u][0], cnt), id[u][0] = cnt;
add_e(++cnt, k ^ 1), add_e(cnt, id[u][1]), id[u][1] = cnt;
}
}
stack st; int ct;
bool instk[5000005];
int dfn[5000005], scc, bl[5000005], low[5000005];
inline void Tarjan(int u)
{
st.push(u); instk[u] = 1;
dfn[u] = low[u] = ++ct;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
else if (instk[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
int v; ++scc;
do
{
v = st.top();
st.pop();
bl[v] = scc;
instk[v] = 0;
} while (u ^ v);
}
}
void dfs(int u, int p1, int p2)
{
if (id[u][0])
{
if (!p1) p1 = id[u][0], p2 = id[u][1];
else
{
add_e(p1, id[u][1]), add_e(id[u][0], p2);
add_e(p1, ++cnt), add_e(id[u][0], cnt), p1 = cnt;
add_e(++cnt, p2), add_e(cnt, id[u][1]), p2 = cnt;
}
}
if (Go[u][0]) dfs(Go[u][0], p1, p2);
if (Go[u][1]) dfs(Go[u][1], p1, p2);
}
int main()
{
int n;
scanf("%d", &n); cnt = 2 * n + 2;
for (int i = 1; i <= n; i++)
{
scanf("%s", ch); insert(ch, i << 1);
if (!count(ch, ch + strlen(ch), '?')) add_e(i << 1 | 1, i << 1);
else insert(ch, i << 1 | 1);
} dfs(0, 0, 0);
for (int i = 1; i <= n; i++)
{
if (!dfn[i << 1]) Tarjan(i << 1);
if (!dfn[i << 1 | 1]) Tarjan(i << 1 | 1);
if (bl[i << 1] == bl[i << 1 | 1]) return !puts("NO");
} puts("YES");
}