Guest User

Untitled

a guest
Dec 8th, 2019
114
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