Codechef 12.4 TSUBSTR 后缀自动机+Trie
题目大意:
给定一棵n个点的有根树,每个节点上都有一个字母,我们说一个字符串出现在这棵树上当且仅当这个字符串能够由树上一条深度递增的路径中的节点上的字母顺次连接起来形成。首先求出现在这棵树上的字符串集合的大小,然后有Q组询问,每次给定一个字母之间的字典序大小,求字符串集合中的字典序第k小的字符串。:
数据范围:n≤250000,q≤50000,1≤k<263,总输出大小不超过800KB。:
算法讨论:
我们不妨考虑后缀自动机在字典树上的拓展,对于每个节点我们都从他的树上的父亲结束插入的节点上开始插入,这样用一次BFS就能完成构造。
后缀自动机可以被看成一张拓扑图,从根节点出发的每条路径都对应着一个子串,那么我们只需要用一次拓扑序动态规划就能求出后缀自动机上从每个节点出发能走出的路径条数了。
对于每组询问,我们可以从根节点出发,类似树上二分的过程,每次按照字母的字典序大小开始走,由于总输出的大小是有限的,所以复杂度是有保证的。
时空复杂度:
时间复杂度O(n+q+800000),空间复杂度O(n|α|)。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 | #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; } |