G

Untitled

public
Guest Oct 29, 2024 Never 7
Clone
C++ paste1.cpp 137 lines (123 loc) | 3.49 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 == 0 ? 0 : st[i].cnt);
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) { // 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 -= st[j].cnt;
112
break;
113
}
114
k -= dp[j];
115
}
116
}
117
return ans;
118
}
119
};
120
121
void solve() {
122
string s; cin >> s;
123
suffix_automaton sa(s);
124
ll k; cin >> k;
125
if(k > 1ll * sz(s) * (sz(s) + 1) / 2) cout << "No such line.\n";
126
else cout << sa.kth_substring(k) << '\n';
127
}
128
129
int main() {
130
Speed();
131
int tc = 1;
132
//cin >> tc;
133
while (tc--) {
134
solve();
135
}
136
return 0;
137
}