Advertisement
smatskevich

Seminar14

May 19th, 2022
656
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. std::vector<int> SuffixArray(const std::string& s) {
  6.   int n = s.length() + 1;
  7.   // Отсортировать по первой букве.
  8.   std::vector<int> c(std::max(256, n));
  9.   for (int i = 0; i < n; ++i) ++c[static_cast<uint8_t>(s[i])];
  10.   for (int i = 1; i < c.size(); ++i) c[i] += c[i - 1];
  11.   std::vector<int> smass(n);
  12.   for (int i = n - 1; i >= 0; --i) {
  13.     smass[--c[static_cast<uint8_t>(s[i])]] = i;
  14.   }
  15.  
  16.   std::vector<int> pockets(n);
  17.   c.assign(n, 0);
  18.   // Заполним первые номера групп и их концы.
  19.   int current_group = 0;
  20.   for (int i = 0; i < n; ++i) {
  21.     if (i != 0 && s[smass[i]] != s[smass[i - 1]]) ++current_group;
  22.     pockets[smass[i]] = current_group;
  23.     c[current_group] = i + 1;  // Текущий конец группы
  24.   }
  25.  
  26.   // Отсортируем по всем остальным
  27.   std::vector<int> smass_new(n);
  28.   std::vector<int> new_pockets(n);
  29.   for (int k = 1; k < n; k <<= 1) {
  30.     for (int i = n - 1; i >= 0; --i) {
  31.       int shifted_suffix = (smass[i] - k + n) % n;
  32.       int pocket = pockets[shifted_suffix];
  33.       smass_new[--c[pocket]] = shifted_suffix;
  34.     }
  35.     std::swap(smass, smass_new);
  36.  
  37.     // Заполним первые номера групп и их концы.
  38.     current_group = 0;
  39.     c.assign(n, 0);
  40.     for (int i = 0; i < n; ++i) {
  41.       if (i != 0 && (pockets[smass[i]] != pockets[smass[i - 1]] ||
  42.           pockets[(smass[i] + k) % n] != pockets[(smass[i - 1] + k) % n])) {
  43.         ++current_group;
  44.       }
  45.       new_pockets[smass[i]] = current_group;
  46.       c[current_group] = i + 1;
  47.     }
  48.     std::swap(pockets, new_pockets);
  49.   }
  50.   return smass;
  51. }
  52.  
  53. std::vector<int> Kasai(const std::vector<int>& smass, const std::string& s) {
  54.   // Построим обратное отображение – для каждого суффикса его позиция в smass.
  55.   // (на самом деле это pockets в конце построения).
  56.   std::vector<int> o(smass.size());
  57.   for (int i = 0; i < smass.size(); ++i) o[smass[i]] = i;
  58.  
  59.   std::vector<int> lcp(smass.size());
  60.   int cur_lcp = 0;
  61.   for (int i = 0; i < s.size(); ++i) {
  62.     if (o[i] == smass.size() - 1) continue;
  63.     int inext = smass[o[i] + 1];
  64.     // Не проверяем выход за границу строки, так как в конце спасительный \0
  65.     for (; s[i + cur_lcp] == s[inext + cur_lcp]; ++cur_lcp);
  66.     lcp[o[i]] = cur_lcp;
  67.     cur_lcp = std::max(0, cur_lcp - 1);
  68.   }
  69.   return lcp;
  70. }
  71.  
  72. int main() {
  73.   std::string s; std::cin >> s;
  74.   std::vector<int> smass = SuffixArray(s);
  75.   for (int v : smass) std::cout << v << "\n";
  76.   std::cout << "Kasai\n";
  77.   std::vector<int> lcp = Kasai(smass, s);
  78.   for (int v : lcp) std::cout << v << "\n";
  79.   return 0;
  80. }
  81.  
Advertisement
RAW Paste Data Copied
Advertisement