G

Untitled

public
Guest Oct 29, 2024 Never 8
Clone
C++ paste1.cpp 138 lines (124 loc) | 3.42 KB
1
#include<bits/stdc++.h>
2
3
using namespace std;
4
typedef long long ll;
5
#define sz(s) (int)(s).size()
6
#define all(s) s.begin(),s.end()
7
8
void Speed() {
9
ios_base::sync_with_stdio(false);
10
cin.tie(NULL);
11
}
12
13
struct suffix_automaton {
14
static const int alpha = 26, offset = 'a';
15
struct state {
16
int len = 0, link = 0, cnt = 0;
17
int next[alpha];
18
state(int len = 0) : len(len) {
19
memset(next, -1, sizeof(next));
20
}
21
state(int len, const state& other) : len(len) {
22
link = other.link;
23
for(int i = 0; i < alpha; i++) {
24
next[i] = other.next[i];
25
}
26
}
27
};
28
29
vector<state> st;
30
vector<ll> dp;
31
int last = 0;
32
suffix_automaton() {
33
st.push_back(state());
34
st[0].link = -1;
35
}
36
37
suffix_automaton(const string &s) : suffix_automaton() {
38
for (char ch : s) extend(ch - offset);
39
dp = vector<ll>(sz(st), -1);
40
calc_number_of_occurrences();
41
}
42
43
void extend(int c) {
44
int cur = sz(st), p = last;
45
st.push_back(state(st[last].len + 1));
46
st[cur].cnt = 1;
47
for(; ~p && st[p].next[c] == -1; p = st[p].link) {
48
st[p].next[c] = cur;
49
}
50
if(p == -1) {
51
st[cur].link = 0;
52
} else {
53
int q = st[p].next[c];
54
if(st[p].len + 1 == st[q].len) {
55
st[cur].link = q;
56
} else {
57
int clone = sz(st);
58
st.push_back(state(st[p].len + 1, st[q]));
59
for(; ~p && st[p].next[c] == q; p = st[p].link) {
60
st[p].next[c] = clone;
61
}
62
st[q].link = st[cur].link = clone;
63
}
64
}
65
last = cur;
66
}
67
68
void calc_number_of_occurrences() {
69
vector<pair<int, int>> v;
70
for (int i = 1; i < sz(st); i++)
71
v.emplace_back(st[i].len, i);
72
73
sort(v.begin(), v.end(), greater<>());
74
75
for (int i = 0; i < sz(st) - 1; i++) {
76
int suf = st[v[i].second].link;
77
st[suf].cnt += st[v[i].second].cnt;
78
}
79
}
80
81
ll num_different_substrings() {
82
ll ans = 0;
83
for(int i = 1; i < sz(st); i++) {
84
ans += st[i].len - st[st[i].link].len;
85
}
86
return ans;
87
}
88
89
ll rec(int i) {
90
auto& ret = dp[i];
91
if(~ret) return ret;
92
ret = !!i;
93
for(int j = 0; j < alpha; j++) {
94
if(~st[i].next[j]) {
95
ret += rec(st[i].next[j]);
96
}
97
}
98
return ret;
99
}
100
101
string kth_substring(ll k) { // non-repeated
102
assert(k <= rec(0));
103
string ans;
104
int cur = 0;
105
while(k > 0) {
106
for(int c = 0; c < 26; c++) {
107
if(st[cur].next[c] == -1) continue;
108
int j = st[cur].next[c];
109
if(dp[j] >= k) {
110
ans += (char)(c + offset); cur = j;
111
k--; break;
112
}
113
k -= dp[j];
114
}
115
}
116
return ans;
117
}
118
};
119
120
void solve() {
121
string s; cin >> s;
122
suffix_automaton sa(s);
123
int q; cin >> q;
124
while(q--){
125
ll k; cin >> k;
126
cout << sa.kth_substring(k) << '\n';
127
}
128
}
129
130
int main() {
131
Speed();
132
int tc = 1;
133
//cin >> tc;
134
while (tc--) {
135
solve();
136
}
137
return 0;
138
}