fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstring>
  4. #include <algorithm>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. // размер алфавита
  10. const int alphabet_size = 256;
  11.  
  12. vector<int> build_lcp(string &line, vector<int> &suf_mas) {
  13.     int n = line.size();
  14.     vector<int> lcp(n);
  15.     vector<int> revers_suf_mus(n); // обратный массив к suf_mas
  16.     for (int i = 0; i < n; i++)
  17.         revers_suf_mus[suf_mas[i]] = i;
  18.     int k = 0;
  19.     for (int i = 0; i < n; i++) {
  20.         if (k > 0)
  21.             k--;
  22.         if (revers_suf_mus[i] == n - 1) {
  23.             lcp[n - 1] = -1;
  24.             k = 0;
  25.         } else {
  26.             int j = suf_mas[revers_suf_mus[i] + 1];
  27.             while (max(i + k, j + k) < n and line[i + k] == line[j + k])
  28.                 k++;
  29.             lcp[revers_suf_mus[i]] = k;
  30.         }
  31.     }
  32.     return lcp;
  33. }
  34.  
  35. vector<int> build_suf_mas(string &line) {
  36.     int number_classes = 1;                     // кол-во классов эквивалентности
  37.     unsigned long n = line.size();              // длина строки
  38.     vector<int> count_letter(alphabet_size, 0); // алфавит - сколько раз встречается буква в строке
  39.     vector<int> permutations(n);                // перестановки циклических строк
  40.     // номер vec_classes[i] класса эквивалентности, которому эта подстрока принадлежит
  41.     vector<int> vec_classes(n);
  42.     /*\
  43.      *  класс эквивалентности следует понимать как сколько суффиксов можно "уместить" в другом суффиксе
  44.      *  к примеру: a, aa, aab, ab - лежат в одном классе эквивалентности
  45.     \*/
  46.     // подсчитаем подсчетом колличество букв
  47.     for (char letter: line)
  48.         count_letter[letter]++;
  49.  
  50.     // подсчитаем начала групп
  51.     for (int i = 1; i < alphabet_size; i++)
  52.         count_letter[i] += count_letter[i - 1];
  53.  
  54.     // расставляем строки в нужном порядке
  55.     for (int i = 0; i < n; i++)
  56.         permutations[--count_letter[line[i]]] = i;
  57.  
  58.     vec_classes[permutations[0]] = 0;
  59.     for (int i = 1; i < n; i++) {
  60.         if (line[permutations[i - 1]] != line[permutations[i]]) number_classes++;
  61.         vec_classes[permutations[i]] = number_classes - 1;
  62.     }
  63.     /*\
  64.      * для подстроки длины 2^k, начинающейся в позиции i,
  65.      * вся необходимая информация содержится в паре чисел (c[i], c[i+2^(k-1)])
  66.     \*/
  67.     vector<int> new_permutations(n); // содержит перестановку в порядке сортировки по вторым элементам пар
  68.     vector<int> vec_classes_new(n); // новые номера классов эквивалентности
  69.     for (unsigned int h = 0; (1 << h) < n; h++) {
  70.         for (int i = 0; i < n; i++) {
  71.             new_permutations[i] = permutations[i] - (1 << h);
  72.             if (new_permutations[i] < 0)
  73.                 new_permutations[i] += n;
  74.         }
  75.         count_letter.assign(number_classes, 0);
  76.         for (int i = 0; i < n; i++)
  77.             count_letter[vec_classes[new_permutations[i]]]++;
  78.         // подсчитаем начала групп
  79.         for (int i = 1; i < number_classes; i++)
  80.             count_letter[i] += count_letter[i - 1];
  81.         for (unsigned long i = n - 1; i > 0; i--)
  82.             permutations[--count_letter[vec_classes[new_permutations[i]]]] = new_permutations[i];
  83.         vec_classes_new[permutations[0]] = 0;
  84.         number_classes = 1;
  85.         for (int i = 1; i < n; i++) {
  86.             int middle_1 = permutations[i] + (1 << h);
  87.             int middle_2 = permutations[i - 1] + (1 << h);
  88.             if (vec_classes[permutations[i]] != vec_classes[permutations[i - 1]] or
  89.                 vec_classes[middle_1] != vec_classes[middle_2])
  90.                 ++number_classes;
  91.             vec_classes_new[permutations[i]] = number_classes - 1;
  92.         }
  93.         vec_classes = vec_classes_new;
  94.     }
  95.     return permutations;
  96. }
  97.  
  98. int number_different_substrings(string &line) {
  99.     line.push_back('\0');
  100.     int n = line.size() - 1;
  101.  
  102.     // suf_mas - суффиксный массив
  103.     vector<int> suf_mas = build_suf_mas(line);
  104.     // массив lcp
  105.     vector<int> lcp = build_lcp(line, suf_mas);
  106.  
  107.     // ответ
  108.     int answer = 0;
  109.     for (int i = 0; i < n; i++)
  110.         answer += n - suf_mas[i] - lcp[i];
  111.     answer += n - suf_mas[n];
  112.     return answer;
  113. }
  114.  
  115. void k_statistick(string s1, string s2, int k) {
  116.     string s = s1 + '#' + s2 + '$' + '\0';
  117.     vector<int> suf_mas = build_suf_mas(s);
  118.     vector<int> lcp = build_lcp(s, suf_mas);
  119.     string c = "";
  120.     int lcp0 = 0;
  121.     int lcp1 = 1000000;
  122.     int lcp2 = 1000000;
  123.     long long increment_res = 0;
  124.     long long res = 0;             // сумарное колличество общих подстрок на данный момент
  125.  
  126.     for (int i = 0; i < suf_mas.size(); i++) {
  127.         if (suf_mas[i] > s2.size()) {
  128.             c.push_back('1');
  129.         } else {
  130.             c.push_back('2');
  131.         }
  132.  
  133.  
  134.         if (c[i - 1] == c[i]) {
  135.             if (c[i] == '1')
  136.                 lcp1 = min(lcp1, lcp[i]);
  137.             if (c[i] == '2')
  138.                 lcp2 = min(lcp2, lcp[i]);
  139.         } else {
  140.  
  141.             if (c[i] == '1') {
  142.                 increment_res = lcp[i] - min(lcp1, lcp0);
  143.                 if (increment_res >= 0) {
  144.                     if (increment_res + res >= k) {
  145.                         for (int h = suf_mas[i]; h <= suf_mas[i] + min(lcp1, lcp0) + k - res - 1; h++)
  146.                             cout << s[h];
  147.                         return;
  148.                     }
  149.                 } else {
  150.                     res += increment_res;
  151.                 }
  152.                 lcp0 = lcp[i];
  153. //                lcp2 = s.size() - suf_mas[i + 1];
  154.             }
  155.             if (c[i] == '2') {
  156.                 increment_res = lcp[i] - min(lcp2, lcp0);
  157.                 if (increment_res >= 0) {
  158.                     if (increment_res + res >= k) {
  159.                         for (int h = suf_mas[i]; h <= suf_mas[i] + min(lcp2, lcp0) + k - res - 1; h++)
  160.                             cout << s[h];
  161.                         return;
  162.                     }
  163.  
  164.                 } else {
  165.                     res += increment_res;
  166.                 }
  167.                 lcp0 = lcp[i];
  168. //                lcp1 = s.size() - suf_mas[i + 1];
  169.             }
  170.         }
  171.     }
  172.  
  173. }
  174.  
  175. int main() {
  176.     string s1, s2;
  177.     int k;
  178.     s1 = "bbbbaaba", s2 = "abbabbabba";
  179.     k = 2;
  180. //    cin >> s1  >> s2 >> k;
  181.     k_statistick(s1, s2, k);
  182.     return 0;
  183. }
  184.  
Success #stdin #stdout 0s 4376KB
comments (?)
stdin
copy 
aaa
abaa
3
stdout
copy 
abb
https://ideone.com/mWtwDV
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!