Advertisement
den4ik2003

Untitled

Dec 23rd, 2023
800
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.14 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <string.h>
  6.  
  7. namespace constants {
  8. const int alphabet_size = 53;
  9. }
  10.  
  11. int char_converse(char symbol) {
  12.   if (symbol == '#') return 0;
  13.   if (symbol >= 'A' and symbol <= 'Z') {
  14.     return symbol - 'A' + 1;
  15.   }
  16.   return symbol - 'a' + 1;
  17. }
  18.  
  19. int main() {
  20.   std::ios_base::sync_with_stdio(false);
  21.   std::cin.tie(nullptr);
  22.  
  23.   std::string s;
  24.   long long k_inp;
  25.   std::cin >> s >> k_inp;
  26.   s += '#';
  27.   int n = s.size();
  28.   std::vector<long long> p(n);
  29.   std::vector<long long> symbols_counter(std::max(n, constants::alphabet_size), 0);
  30.   std::vector<long long> eq_classes(n);
  31.   std::vector<long long> lcp(n);
  32.   std::vector<long long> pos(n);
  33.  
  34.   // zero-step
  35.   for (char symbol : s) {
  36.     ++symbols_counter[char_converse(symbol)];
  37.   }
  38.   for (int i = 1; i < constants::alphabet_size; ++i) {
  39.     symbols_counter[i] += symbols_counter[i - 1];
  40.   }
  41.   for (int i = n - 1; i >= 0; --i) {
  42.     p[--symbols_counter[char_converse(s[i])]] = i;
  43.   }
  44.  
  45.   eq_classes[p[0]] = 0;
  46.   for (int i = 1; i < n; ++i) {
  47.     eq_classes[p[i]] = eq_classes[p[i - 1]];
  48.     if (s[p[i]] != s[p[i - 1]]) {
  49.       ++eq_classes[p[i]];
  50.     }
  51.   }
  52.  
  53.   // k-step
  54.   for (int k = 0; (1 << k) < n; ++k) { // TODO: k здесь от одного или нет?
  55.     std::vector<int> p_new(n);
  56.     for (int i = 0; i < n; ++i) {
  57.       p_new[i] = p[i] - (1 << k);
  58.       if (p_new[i] < 0) {
  59.         p_new[i] += n;
  60.       }
  61.     }
  62.     symbols_counter.assign(symbols_counter.size(), 0);
  63. //     memset(&symbols_counter, 0, sizeof(symbols_counter));
  64.     for (int i = 0; i < n; ++i) {
  65.       ++symbols_counter[eq_classes[i]];
  66.     }
  67.     for (int i = 1; i < n; ++i) {
  68.       symbols_counter[i] += symbols_counter[i - 1];
  69.     }
  70.     for (int i = n - 1; i >= 0; --i) {
  71.       p[--symbols_counter[eq_classes[p_new[i]]]] = p_new[i];
  72.     }
  73.     std::vector<long long> new_eq(n);
  74.     new_eq[p[0]] = 0;
  75.     for (int i = 1; i < n; ++i) {
  76.       new_eq[p[i]] = new_eq[p[i - 1]];
  77.       if (eq_classes[p[i]] != eq_classes[p[i - 1]]) {
  78.         ++new_eq[p[i]];
  79.       } else if (eq_classes[(p[i] + (1 << k)) % n] != eq_classes[(p[i - 1] + (1 << k)) % n]) {
  80.         ++new_eq[p[i]];
  81.       }
  82.     }
  83.     eq_classes = new_eq;
  84.   }
  85.  
  86.   for (int i = 0; i < n; ++i) {
  87.     pos[p[i]] = i;
  88.   }
  89.  
  90.   int l = 0;
  91.   for (int i = 0; i < n; i++) {
  92.     l = std::max(l - 1, 0);
  93.     if (pos[i] == n - 1) {
  94.       continue;
  95.     }
  96.     int j = p[pos[i] + 1];
  97.     while (s[i + l] == s[j + l]) {
  98.       ++l;
  99.     }
  100.     lcp[pos[i]] = l;
  101.   }
  102.  
  103.   long long cmpval = n - p[0] - 1;
  104.   for (int i = 1; i < n; ++i) {
  105.     cmpval += (n - p[i] - 1 - lcp[i - 1]);
  106.   }
  107.  
  108.   if (k_inp < cmpval) {
  109.     long long cumsumma = 0, i = -1;
  110.     while (cumsumma < k_inp) {
  111.       ++i;
  112.       cumsumma += n - p[i] - lcp[i - 1] - 1;
  113.       if (i == 0) {
  114.         cumsumma += lcp[i - 1];
  115.       }
  116.     }
  117.     int ll;
  118.     for (int j = p[i]; j < (n - 1) - cumsumma + k_inp; ++j) {
  119.       std::cout << s[j];
  120.     }
  121. //    std::cout << "\n";
  122.   } else {
  123.     for (int j = p[n - 1]; j <= n - 2; ++j) {
  124.       std::cout << s[j];
  125.     }
  126. //    std::cout << "\n";
  127.   }
  128. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement