#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;
// размер алфавита
const int alphabet_size = 256;
vector<int> build_lcp(string &line, vector<int> &suf_mas) {
int n = line.size();
vector<int> lcp(n);
vector<int> revers_suf_mus(n); // обратный массив к suf_mas
for (int i = 0; i < n; i++)
revers_suf_mus[suf_mas[i]] = i;
int k = 0;
for (int i = 0; i < n; i++) {
if (k > 0)
k--;
if (revers_suf_mus[i] == n - 1) {
lcp[n - 1] = -1;
k = 0;
} else {
int j = suf_mas[revers_suf_mus[i] + 1];
while (max(i + k, j + k) < n and line[i + k] == line[j + k])
k++;
lcp[revers_suf_mus[i]] = k;
}
}
return lcp;
}
vector<int> build_suf_mas(string &line) {
int number_classes = 1; // кол-во классов эквивалентности
unsigned long n = line.size(); // длина строки
vector<int> count_letter(alphabet_size, 0); // алфавит - сколько раз встречается буква в строке
vector<int> permutations(n); // перестановки циклических строк
// номер vec_classes[i] класса эквивалентности, которому эта подстрока принадлежит
vector<int> vec_classes(n);
/*\
* класс эквивалентности следует понимать как сколько суффиксов можно "уместить" в другом суффиксе
* к примеру: a, aa, aab, ab - лежат в одном классе эквивалентности
\*/
// подсчитаем подсчетом колличество букв
for (char letter: line)
count_letter[letter]++;
// подсчитаем начала групп
for (int i = 1; i < alphabet_size; i++)
count_letter[i] += count_letter[i - 1];
// расставляем строки в нужном порядке
for (int i = 0; i < n; i++)
permutations[--count_letter[line[i]]] = i;
vec_classes[permutations[0]] = 0;
for (int i = 1; i < n; i++) {
if (line[permutations[i - 1]] != line[permutations[i]]) number_classes++;
vec_classes[permutations[i]] = number_classes - 1;
}
/*\
* для подстроки длины 2^k, начинающейся в позиции i,
* вся необходимая информация содержится в паре чисел (c[i], c[i+2^(k-1)])
\*/
vector<int> new_permutations(n); // содержит перестановку в порядке сортировки по вторым элементам пар
vector<int> vec_classes_new(n); // новые номера классов эквивалентности
for (unsigned int h = 0; (1 << h) < n; h++) {
for (int i = 0; i < n; i++) {
new_permutations[i] = permutations[i] - (1 << h);
if (new_permutations[i] < 0)
new_permutations[i] += n;
}
count_letter.assign(number_classes, 0);
for (int i = 0; i < n; i++)
count_letter[vec_classes[new_permutations[i]]]++;
// подсчитаем начала групп
for (int i = 1; i < number_classes; i++)
count_letter[i] += count_letter[i - 1];
for (unsigned long i = n - 1; i > 0; i--)
permutations[--count_letter[vec_classes[new_permutations[i]]]] = new_permutations[i];
vec_classes_new[permutations[0]] = 0;
number_classes = 1;
for (int i = 1; i < n; i++) {
int middle_1 = permutations[i] + (1 << h);
int middle_2 = permutations[i - 1] + (1 << h);
if (vec_classes[permutations[i]] != vec_classes[permutations[i - 1]] or
vec_classes[middle_1] != vec_classes[middle_2])
++number_classes;
vec_classes_new[permutations[i]] = number_classes - 1;
}
vec_classes = vec_classes_new;
}
return permutations;
}
int number_different_substrings(string &line) {
line.push_back('\0');
int n = line.size() - 1;
// suf_mas - суффиксный массив
vector<int> suf_mas = build_suf_mas(line);
// массив lcp
vector<int> lcp = build_lcp(line, suf_mas);
// ответ
int answer = 0;
for (int i = 0; i < n; i++)
answer += n - suf_mas[i] - lcp[i];
answer += n - suf_mas[n];
return answer;
}
void k_statistick(string s1, string s2, int k) {
string s = s1 + '#' + s2 + '$' + '\0';
vector<int> suf_mas = build_suf_mas(s);
vector<int> lcp = build_lcp(s, suf_mas);
string c = "";
int lcp0 = 0;
int lcp1 = 1000000;
int lcp2 = 1000000;
long long increment_res = 0;
long long res = 0; // сумарное колличество общих подстрок на данный момент
for (int i = 0; i < suf_mas.size(); i++) {
if (suf_mas[i] > s2.size()) {
c.push_back('1');
} else {
c.push_back('2');
}
if (c[i - 1] == c[i]) {
if (c[i] == '1')
lcp1 = min(lcp1, lcp[i]);
if (c[i] == '2')
lcp2 = min(lcp2, lcp[i]);
} else {
if (c[i] == '1') {
increment_res = lcp[i] - min(lcp1, lcp0);
if (increment_res >= 0) {
if (increment_res + res >= k) {
for (int h = suf_mas[i]; h <= suf_mas[i] + min(lcp1, lcp0) + k - res - 1; h++)
cout << s[h];
return;
}
} else {
res += increment_res;
}
lcp0 = lcp[i];
// lcp2 = s.size() - suf_mas[i + 1];
}
if (c[i] == '2') {
increment_res = lcp[i] - min(lcp2, lcp0);
if (increment_res >= 0) {
if (increment_res + res >= k) {
for (int h = suf_mas[i]; h <= suf_mas[i] + min(lcp2, lcp0) + k - res - 1; h++)
cout << s[h];
return;
}
} else {
res += increment_res;
}
lcp0 = lcp[i];
// lcp1 = s.size() - suf_mas[i + 1];
}
}
}
}
int main() {
string s1, s2;
int k;
s1 = "bbbbaaba", s2 = "abbabbabba";
k = 2;
// cin >> s1 >> s2 >> k;
k_statistick(s1, s2, k);
return 0;
}