SHARE
TWEET

Untitled

a guest Dec 8th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. vector<int> lcp, ind, sr, ps;
  2. map<int, vector<int>> ids;
  3.  
  4. vector<int> calc_lcp(string &val, vector<int> &c, vector<int> &p) {
  5.     int n = len(val);
  6.     int current_lcp = 0;
  7.     vector<int> lcp(n);
  8.     for (int i = 0; i < n; i++) {
  9.         if (c[i] == n - 1)
  10.             continue;
  11.         int nxt = p[c[i] + 1];
  12.         while (max(i, nxt) + current_lcp < n && val[i + current_lcp] == val[nxt + current_lcp])
  13.             current_lcp++;
  14.         lcp[c[i]] = current_lcp;
  15.         current_lcp = max(0ll, current_lcp - 1);
  16.     }
  17.     return lcp;
  18. }
  19.  
  20. vector<int> suffix_array(string &s) {
  21.     s.push_back(0);  
  22.     int n = len(s),cnt = 0, cls = 0;  
  23.     vector<int> c(n), p(n);
  24.      
  25.     map<int, vector<int>> t;
  26.     for (int i = 0; i < n; i++)
  27.         t[s[i]].push_back(i);
  28.      
  29.     for (auto &x : t) {
  30.         for (int u : x.y)
  31.             c[u] = cls, p[cnt++] = u;
  32.         cls++;
  33.     }
  34.      
  35.     for (int l = 1; cls < n; l++) {
  36.         vector<vector<int>> a(cls);  
  37.         vector<int> _c(n);  
  38.         int d = (1 << l) / 2;
  39.         int _cls = cnt = 0;  
  40.          
  41.         for (int i = 0; i < n; i++) {
  42.             int k = (p[i] - d + n) % n;
  43.             a[c[k]].push_back(k);
  44.         }
  45.          
  46.         for (int i = 0; i < cls; i++) {
  47.             for (int j = 0; j < len(a[i]); j++) {
  48.                 if (j == 0 || c[(a[i][j] + d) % n] != c[(a[i][j - 1] + d) % n])
  49.                     _cls++;
  50.                 _c[a[i][j]] = _cls - 1;
  51.                 p[cnt++] = a[i][j];
  52.             }
  53.         }
  54.          
  55.         c = _c;
  56.         cls = _cls;
  57.     }
  58.      
  59.     lcp = calc_lcp(s, c, p);
  60.     return vector<int>(p.begin() + 1, p.end());
  61. }
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