# 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