题意
把一个字符串所有的不同的字串全拿出来，按字典序排序，第k小的字符串是什么样子的呢？
思路
字串问题当然是后缀自动机了。对于给出的字符串，建立一个后缀自动机，然后对后缀自动机对应的状态图进行一次拓扑排序，每个节点的深度就是节点上携带的mxn(当前状态对应的字串最长为多少位)。接下来我们从深度最大的节点开始往根部处理每一个节点，我们要求出的就是对于每个能走的边，所有接下来的以这条边对应的字母开头的字串数目，而节点上面存的是节点出边的边权之和。这样我们就得到了一个处理好的图，我们只要在这个图上面搜索，逼近k值就可以了。
因为SPOJ卡常数特别严重，所以拓扑排序要使用计数排序的方法，而且要开额外的数组纪录每一个节点所有的孩子来加快之后的搜索速度。
代码
|
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 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 |
// // SPOJ SUBLEX.cpp // playground // // Created by Adam Chang on 2015/08/10. // Copyright © 2015年 Adam Chang. All rights reserved. // #include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> using namespace std; #define MAXN 90005 struct SAM_State{ int mxn; int cnt; int id; SAM_State *to[26]; SAM_State *parent; void init(int _mxn){ mxn = _mxn; memset(to, NULL, sizeof(to)); parent = NULL; cnt = 0; id = 0; } } idx[2*MAXN]; int totalNode = 0; int len = 0; SAM_State *idx_sorted[2*MAXN]; SAM_State* SAM_Append(SAM_State *last,SAM_State *root,int ch){ SAM_State *p = last; SAM_State *np = &idx[++totalNode]; np -> mxn = p -> mxn + 1; while (p && p -> to[ch] == NULL) { p -> to[ch] = np; p = p -> parent; } if (p != NULL) { SAM_State *q = p -> to[ch]; if (q -> mxn == p -> mxn + 1) { np -> parent = q; }else{ SAM_State *nq = &idx[++totalNode]; *nq = *q; nq -> mxn = p -> mxn + 1; q -> parent = nq; np -> parent = nq; while (p && p -> to[ch] == q) { p -> to[ch] = nq; p = p -> parent; } } }else{ np -> parent = root; } last = np; return last; } void SAM_Init(int n){ for (int i = 0; i <= n ; i++) { idx[i].init(0); } totalNode = 0; } SAM_State* SAM_Build(char* str){ len = (int)strlen(str); SAM_Init(2*len); SAM_State *root = &idx[0]; SAM_State *last = root; for (int i = 0; i < len; i++) { last = SAM_Append(last, root, str[i] - 'a'); } return root; } int cnt[MAXN*2]; void SAM_Toposort(){ for (int i = 0; i <= totalNode; i++) { idx[i].id = i; cnt[idx[i].mxn]++; } for (int i = 1; i <= len; i++) { cnt[i] += cnt[i-1]; } for (int i = 0; i <= totalNode; i++) { idx_sorted[--cnt[idx[i].mxn]] = &idx[i]; } } int childID[MAXN*2][26]; int childVal[MAXN*2][26]; char childCh[MAXN*2][26]; int childCnt[MAXN*2]; void SAM_Buildgraph(){ for (int i = totalNode; i >= 0; i--) { SAM_State *cur = idx_sorted[i]; int curid = cur -> id; for (int j = 0; j < 26; j++) { if (cur -> to[j] != NULL) { SAM_State *nxt = cur -> to[j]; int nxtid = nxt -> id; childID[curid][childCnt[curid]] = nxtid; childVal[curid][childCnt[curid]] = nxt -> cnt + 1; childCh[curid][childCnt[curid]] = j + 'a'; cur -> cnt += nxt -> cnt + 1; childCnt[curid]++; } } } } char ans[MAXN]; void get_ans(int k){ int pos = 0; SAM_State *cur = &idx[0]; while (k) { for (int i = 0; i < childCnt[cur -> id]; i++) { if (childVal[cur -> id][i] < k) { k -= childVal[cur -> id][i]; }else { k--; ans[pos] = childCh[cur -> id][i]; cur = &idx[childID[cur -> id][i]]; pos++; break; } } } ans[pos] = '\0'; puts(ans); } char a[MAXN]; int main(){ scanf(" %s",a); SAM_Build(a); SAM_Toposort(); SAM_Buildgraph(); int q = 0; scanf(" %d",&q); for (int i = 1; i <= q; i++) { int k = 0; scanf(" %d",&k); get_ans(k); } return 0; } |
