SHARE
TWEET

SuffixArray simple v2

999ms Feb 20th, 2020 78 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. struct SuffixArray {
  2.   string s;
  3.   int n;
  4.   vector<int> arr;
  5.   #define modulo(x) (x >= n ? x - n : x)
  6.   SuffixArray(const string& str)
  7.     : s(str + char(0))
  8.     , n(size(s))
  9.     , arr(n)
  10.   {
  11.     vector<int> c(n), buff(c);
  12.     iota(all(arr), 0);
  13.     for (int deg = 0; (1 << (deg - 1)) < n; deg++) {
  14.       if (deg == 0) {
  15.         sort(all(arr), [&] (int i, int j) { return s[i] < s[j]; });
  16.         for (int i = 1; i < n; i++) {
  17.           c[arr[i]] = c[arr[i - 1]] + (s[arr[i]] == s[arr[i - 1]] ? 0 : 1);
  18.         }
  19.       } else {
  20.         int len = 1 << (deg - 1);
  21.         for (int i = 1, j = 1; i < n; i = j) {
  22.           while (j < n && c[arr[i]] == c[arr[j]]) j++;  
  23.           sort(begin(arr) + i, begin(arr) + j, [&] (int a, int b) {
  24.             return c[modulo(a + len)] < c[modulo(b + len)];
  25.           });
  26.         }
  27.         for (int i = 1; i < n; i++) {
  28.           buff[arr[i]] = buff[arr[i - 1]];
  29.           if (c[arr[i]] != c[arr[i - 1]] || c[modulo(arr[i] + len)] != c[modulo(arr[i - 1] + len)]) {
  30.             buff[arr[i]]++;
  31.           }
  32.         }
  33.         copy(all(buff), begin(c));
  34.       }
  35.     }
  36.   }
  37.   void Print() {
  38.     for (int val : arr) {
  39.       cout << val << ' ';
  40.     }
  41.     cout << '\n';
  42.   }
  43.   #undef modulo
  44. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top