C.cpp

#include <iostream>
#include <string>
#include <vector>

const size_t alphabet_size = 256;

void BuildLcp(std::vector<size_t> &lcp, const std::vector<size_t> &suf_array,
              std::string &text) {
  size_t text_size = text.size();
  size_t min_value_lcp = 0;
  auto rsuf_aray = new size_t[text_size];  // reverse function
  for (size_t i = 0; i < text_size; ++i) {
    rsuf_aray[suf_array[i]] = i;
  }
  for (size_t i = 0; i < text_size; ++i) {
    min_value_lcp > 0 ? --min_value_lcp : 0;
    if (rsuf_aray[i] == text_size - 1) {
      min_value_lcp = 0;
      continue;
    }
    size_t j = suf_array[rsuf_aray[i] + 1];
    while ((std::max(i + min_value_lcp, j + min_value_lcp) < text_size) &&
           (text[i + min_value_lcp] == text[j + min_value_lcp])) {
      ++min_value_lcp;
    }
    lcp[rsuf_aray[i]] = min_value_lcp;
  }
  delete[] rsuf_aray;
}

void ContinueBuildingSufArr(std::string &text, std::vector<size_t> &suf_array,
                            std::vector<size_t> &classes, size_t &num_class) {
  size_t text_size = text.size();
  auto half_suf = new size_t[text_size];
  std::vector<size_t> new_classes(text_size);
  for (size_t pow = 0; (1 << pow) < text_size; ++pow) {
    size_t pow_of_2 = (1 << pow);
    std::vector<size_t> cnt(num_class);
    for (size_t i = 0; i < text_size; ++i) {
      half_suf[i] = (suf_array[i] - pow_of_2 + text_size) % text_size;
    }
    for (size_t i = 0; i < text_size; ++i) {
      ++cnt[classes[half_suf[i]]];
    }
    for (size_t i = 1; i < num_class; ++i) {
      cnt[i] += cnt[i - 1];
    }
    for (size_t i = 0; i < text_size; ++i) {
      suf_array[--cnt[classes[half_suf[text_size - 1 - i]]]] =
          half_suf[text_size - 1 - i];
    }
    size_t last_class = 0;
    new_classes[suf_array[0]] = 0;
    size_t mid1;
    size_t mid2;
    for (size_t i = 1; i < text_size; ++i) {
      mid1 = (suf_array[i - 1] + pow_of_2) % text_size;
      mid2 = (suf_array[i] + pow_of_2) % text_size;
      if ((classes[suf_array[i]] != classes[suf_array[i - 1]]) ||
          (classes[mid1] != classes[mid2])) {
        ++last_class;
      }
      new_classes[suf_array[i]] = last_class;
    }
    classes = new_classes;
    num_class = last_class + 1;
  }
  delete[] half_suf;
}

void BuildSufArray(std::string &text, std::vector<size_t> &suff_array,
                   std::vector<size_t> &classes) {
  size_t text_size = text.size();
  std::vector<size_t> cnt(alphabet_size);
  for (size_t i = 0; i < text_size; ++i) {
    ++cnt[text[i]];
  }
  for (size_t i = 1; i < alphabet_size; ++i) {
    cnt[i] += cnt[i - 1];
  }
  for (size_t i = 0; i < text_size; ++i) {
    suff_array[--cnt[text[i]]] = i;  // p[--cnt[s[i]]] = i
  }
  size_t last_class = 0;
  classes[suff_array[0]] = 0;
  for (size_t i = 1; i < text_size; ++i) {
    if (text[suff_array[i]] != text[suff_array[i - 1]]) {
      ++last_class;
    }
    classes[suff_array[i]] = last_class;
  }
  ++last_class;
  ContinueBuildingSufArr(text, suff_array, classes, last_class);
}

std::string Solve(std::string &text, const int64_t &k, const size_t &s1_size,
                  const size_t &s2_size) {
  size_t text_size = text.size();
  std::vector<size_t> suf_array(text_size);
  std::vector<size_t> classes(text_size);
  std::vector<size_t> lcp(text_size);
  BuildSufArray(text, suf_array, classes);
  BuildLcp(lcp, suf_array, text);
  size_t min_lcp = 0;
  size_t i = 2;
  int64_t counter = 0;
  while ((counter < k) && (i < text_size - 1)) {
    if (((suf_array[i] < s1_size) && (suf_array[i + 1] > s1_size)) ||
        ((suf_array[i] > s1_size) && (suf_array[i + 1] < s1_size))) {
      counter += lcp[i] - std::min(lcp[i], min_lcp);
      min_lcp = lcp[i];
      ++i;
      continue;
    }
    min_lcp = std::min(min_lcp, lcp[i]);
    ++i;
  }
  if (counter < k) {
    return "-1";
  }
  return text.substr(suf_array[i - 1], min_lcp - (counter - k));
}

int main() {
  std::string s1;
  std::string s2;
  std::string text;
  size_t s1_size;
  size_t s2_size;
  int64_t k;
  std::cin >> s1 >> s2 >> k;
  text = s1 + '`' + s2 + '_';
  s1_size = s1.size();
  s2_size = s2.size();
  std::cout << Solve(text, k, s1_size, s2_size) << '\n';
  return 0;
}