Advertisement
999ms

SuffixArray

Feb 20th, 2020
308
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define all(x) begin(x),end(x)
  3. #define make_unique(x) if (!is_sorted(all(x))) sort(all(x)); x.erase(unique(all(x)), x.end());
  4. #define remax(x,y) (x > y ? x = y, true : false)
  5. #define remin(x,y) (x < y ? x = y, true : false)
  6. #define size(x) int(x.size())
  7.  
  8. using namespace std;
  9. using ll = long long;
  10.  
  11. struct SuffixArray {
  12.   const string s;
  13.   const int n;
  14.   vector<int> arr;
  15.   #define modulo(x) (x >= n ? x - n : x)
  16.   SuffixArray(const string& str)
  17.     : s(str + char(0))
  18.     , n(size(s))
  19.     , arr(n)
  20.   {
  21.     vector<int> c(n), buff(n), ind(n), cnt(n);
  22.     iota(all(arr), 0);
  23.     vector<int> mp(256);
  24.     for (int i = 0; i < n; i++) { mp[s[i]]++; }
  25.     for (int i = 1; i < 256; i++) { mp[i] += mp[i - 1]; }
  26.     for (int i = n - 1; i >= 0; i--) { arr[--mp[s[i]]] = i; }
  27.     c[arr[0]] = 0;
  28.     for (int i = 1; i < n; i++) {
  29.       c[arr[i]] = c[arr[i - 1]];
  30.       if (s[arr[i]] != s[arr[i - 1]]) {
  31.         c[arr[i]]++;
  32.       }
  33.     }
  34.     for (int deg = 1; (1 << (deg - 1)) < n; deg++) {
  35.       const int len = 1 << (deg - 1);
  36.       fill(all(cnt), 0);
  37.       ind[0] = 0;
  38.       for (int i = 0; i < n; i++) {
  39.         arr[i] -= len;
  40.         if (arr[i] < 0) arr[i] += n;
  41.       }
  42.       for (int i = 0; i < n; i++) { cnt[c[arr[i]]]++; }
  43.       for (int i = 1; i < n; i++) { ind[i] = ind[i - 1] + cnt[i - 1]; }
  44.       for (int i = 0; i < n; i++) { buff[ind[c[arr[i]]]++] = arr[i]; }
  45.       copy(all(buff), begin(arr));
  46.      
  47.       buff[arr[0]] = 0;
  48.       for (int i = 1; i < n; i++) {
  49.         buff[arr[i]] = buff[arr[i - 1]];
  50.         if (c[arr[i]] != c[arr[i - 1]] || c[modulo(arr[i] + len)] != c[modulo(arr[i - 1] + len)]) {
  51.           buff[arr[i]]++;
  52.         }
  53.       }
  54.       copy(all(buff), begin(c));
  55.     }
  56.   }
  57.   void Print() {
  58.     for (int val : arr) {
  59.       cout << val << ' ';
  60.     }
  61.     cout << endl;
  62.   }
  63.   #undef modulo
  64. };
  65.  
  66. int main() {
  67.   ios_base::sync_with_stdio(false);
  68.   cin.tie(nullptr);
  69.   cout.tie(nullptr);
  70.   string s;
  71.   cin >> s;
  72.   SuffixArray arr(s);
  73.   arr.Print();
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement