SUBLEX - Lexicographical Substring Search
suffix-array-8
Little Daniel loves to play with strings! He always finds different ways to have fun with strings! Knowing that, his friend Kinan decided to test his skills so he gave him a string S and asked him Q questions of the form:
If all distinct substrings of string S were sorted lexicographically, which one will be the K-th smallest?
After knowing the huge number of questions Kinan will ask, Daniel figured out that he can’t do this alone. Daniel, of course, knows your exceptional programming skills, so he asked you to write him a program which given S will answer Kinan’s questions.
Example:
S = “aaa” (without quotes)
substrings of S are “a” , “a” , “a” , “aa” , “aa” , “aaa”. The sorted list of substrings will be:
“a”, “aa”, “aaa”.
Input
In the first line there is Kinan’s string S (with length no more than 90000 characters). It contains only small letters of English alphabet. The second line contains a single integer Q (Q <= 500) , the number of questions Daniel will be asked. In the next Q lines a single integer K is given (0 < K < 2^31).
Output
Output consists of Q lines, the i-th contains a string which is the answer to the i-th asked question.
Example
Input:
aaa
2
2
3
Output:
aa
aaa
题目链接：SPOJ SUBLEX
题意就是询问去重后的第$K$小子串，我们用栈+回溯$dfs$一次$parent$树可以直接输出字典序从小到大的子串，可以记录一下某一个节点的子树一共可以构成几个子串，显然这些子串都是连续的，把每一个节点初始赋值权值$1$，然后按照$parent$叠加就可以得到子树的权值，此时任意一个节点的值就是这个节点结尾的字典序上连续的子串个数；假设当前节点$u$控制了$A$种连续字典序子串，当前要查询第$k$小子串，如果$k \le A$，那么显然答案在这个点的子树中，因此往这个点走，但是走过之后这个节点本身已经不能算子串了，因此要$k=k-1$；否则显然是$k-=A$，即直接排除掉$u$上的所有子串情况。
代码：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
using namespace std;
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const int N = 90010;
struct Trie
{
int nxt[26], pre, len;
LL cnt;
void init()
{
for (int i = 0; i < 26; ++i)
nxt[i] = -1;
pre = -1;
cnt = 1;
}
} L[N << 1];
int sz, last;
char s[N];
int cnt[N], x[N << 1];
int ans[N];
inline void init()
{
sz = last = 0;
L[sz++].init();
//L[0].cnt = 0;
CLR(cnt, 0);
CLR(ans, 0);
}
inline int newnode()
{
L[sz].init();
return sz++;
}
void ins(int c)
{
int u = newnode();
L[u].len = L[last].len + 1;
int t = last;
while (t != -1 && L[t].nxt[c] == -1)
{
L[t].nxt[c] = u;
t = L[t].pre;
}
if (t == -1)
L[u].pre = 0;
else
{
int v = L[t].nxt[c];
if (L[t].len + 1 == L[v].len)
L[u].pre = v;
else
{
int np = newnode();
L[np] = L[v];
L[np].len = L[t].len + 1;
L[np].pre = L[v].pre;
L[u].pre = L[v].pre = np;
while (t != -1 && L[t].nxt[c] == v)
{
L[t].nxt[c] = np;
t = L[t].pre;
}
}
}
last = u;
}
int main(void)
{
int i, j, q;
LL k;
while (~scanf("%s", s))
{
init();
int len = strlen(s);
for (i = 0; i < len; ++i)
ins(s[i] - 'a');
for (i = 0; i < sz; ++i)
++cnt[L[i].len];
for (i = 1; i <= len; ++i)
cnt[i] += cnt[i - 1];
for (i = sz - 1; i >= 0; --i)
x[--cnt[L[i].len]] = i;
for (i = sz - 1; i >= 0; --i)
{
int u = x[i];
for (j = 0; j < 26; ++j)
{
int v = L[u].nxt[j];
if (~v)
L[u].cnt += L[v].cnt;
}
}
scanf("%d", &q);
while (q--)
{
scanf("%lld", &k);
int u = 0;
while (k)
{
for (i = 0; i < 26; ++i)
{
int v = L[u].nxt[i];
if (v == -1)
continue;
if (k <= L[v].cnt)
{
--k;
putchar(i + 'a');
u = v;
break;
}
else
k -= L[v].cnt;
}
}
puts("");
}
}
return 0;
}