Codechef 12.4 TSUBSTR 后缀自动机+Trie
题目大意：
给定一棵$n$个点的有根树，每个节点上都有一个字母，我们说一个字符串出现在这棵树上当且仅当这个字符串能够由树上一条深度递增的路径中的节点上的字母顺次连接起来形成。首先求出现在这棵树上的字符串集合的大小，然后有$Q$组询问，每次给定一个字母之间的字典序大小，求字符串集合中的字典序第$k$小的字符串。：
数据范围：$n\leq{250000},q\leq{50000},1\leq{k}<2^{63}$，总输出大小不超过$800KB$。：
算法讨论：
我们不妨考虑后缀自动机在字典树上的拓展，对于每个节点我们都从他的树上的父亲结束插入的节点上开始插入，这样用一次BFS就能完成构造。
后缀自动机可以被看成一张拓扑图，从根节点出发的每条路径都对应着一个子串，那么我们只需要用一次拓扑序动态规划就能求出后缀自动机上从每个节点出发能走出的路径条数了。
对于每组询问，我们可以从根节点出发，类似树上二分的过程，每次按照字母的字典序大小开始走，由于总输出的大小是有限的，所以复杂度是有保证的。
时空复杂度：
时间复杂度$O(n+q+800000)$，空间复杂度$O(n|\alpha|)$。
代码：
#include <cstdio>
#include <cstring>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
#define N 250010
int pa[N << 1], len[N << 1], tr[N << 1][26], cnt, root;
int newnode(int _len) {
len[++cnt] = _len;
return cnt;
}
char ch[N];
int head[N], nxt[N << 1], to[N << 1];
void addedge(int a, int b) {
static int q = 1;
to[q] = b;
nxt[q] = head[a];
head[a] = q++;
}
void make(int a,int b) {
addedge(a, b);
addedge(b, a);
}
void dfs(int x, int dep, int fa, int last) {
static int p, np, q, nq, temp, y;
y = ch[x] - 'a';
if ((q = tr[last][y])) {
if (len[q] != dep) {
temp = newnode(dep);
pa[temp] = pa[q];
pa[q] = temp;
memcpy(tr[temp], tr[q], sizeof tr[q]);
for (p = last; p && tr[p][y] == q; p = pa[p])
tr[p][y] = temp;
last = temp;
}
else
last = q;
}
else {
np = newnode(dep);
for (p = last; p && !tr[p][y]; p = pa[p])
tr[p][y] = np;
if (!p)
pa[np] = root;
else {
if (len[q = tr[p][y]] == len[p] + 1)
pa[np] = q;
else {
nq = newnode(len[p] + 1);
pa[nq] = pa[q];
pa[q] = pa[np] = nq;
memcpy(tr[nq], tr[q], sizeof tr[q]);
for (; p && tr[p][y] == q; p = pa[p])
tr[p][y] = nq;
}
}
last = np;
}
for (int j = head[x]; j; j = nxt[j])
if (to[j] != fa)
dfs(to[j], dep + 1, x, last);
}
int in[N << 1];
int q[N << 1], fr, ta;
ll f[N << 1];
char per[26];
void getAns(int x, ll k) {
if (k == 1)
return;
--k;
for (int i = 0; i < 26; ++i) {
if (f[tr[x][per[i] - 'a']] >= k) {
putchar(per[i]);
getAns(tr[x][per[i] - 'a'], k);
return;
}
else
k -= f[tr[x][per[i] - 'a']];
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("tt.in", "r", stdin);
#endif
int n, Q;
cin >> n >> Q;
scanf("%s", ch + 1);
int a, b, i, j;
for (i = 1; i < n; ++i) {
scanf("%d%d", &a, &b);
make(a, b);
}
root = newnode(0);
dfs(1, 1, -1, root);
for (i = 1; i <= cnt; ++i)
for (j = 0; j < 26; ++j)
if (tr[i][j])
++in[tr[i][j]];
q[ta++] = 1;
while (fr != ta) {
i = q[fr++];
for (j = 0; j < 26; ++j)
if (tr[i][j]) {
if (!(--in[tr[i][j]]))
q[ta++] = tr[i][j];
}
}
for (i = cnt - 1; i >= 0; --i) {
f[q[i]] = 1;
for (j = 0; j < 26; ++j)
if (tr[q[i]][j])
f[q[i]] += f[tr[q[i]][j]];
}
ll total = f[1];
cout << total << endl;
ll k;
while (Q--) {
scanf("%s%I64d", per, &k);
if (k > total)
puts("-1");
else {
getAns(1, k);
puts("");
}
}
return 0;
}
评论 (0)