Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- vector<int> lcp, ind, sr, ps;
- map<int, vector<int>> ids;
- vector<int> calc_lcp(string &val, vector<int> &c, vector<int> &p) {
- int n = len(val);
- int current_lcp = 0;
- vector<int> lcp(n);
- for (int i = 0; i < n; i++) {
- if (c[i] == n - 1)
- continue;
- int nxt = p[c[i] + 1];
- while (max(i, nxt) + current_lcp < n && val[i + current_lcp] == val[nxt + current_lcp])
- current_lcp++;
- lcp[c[i]] = current_lcp;
- current_lcp = max(0ll, current_lcp - 1);
- }
- return lcp;
- }
- vector<int> suffix_array(string &s) {
- s.push_back(0);
- int n = len(s),cnt = 0, cls = 0;
- vector<int> c(n), p(n);
- map<int, vector<int>> t;
- for (int i = 0; i < n; i++)
- t[s[i]].push_back(i);
- for (auto &x : t) {
- for (int u : x.y)
- c[u] = cls, p[cnt++] = u;
- cls++;
- }
- for (int l = 1; cls < n; l++) {
- vector<vector<int>> a(cls);
- vector<int> _c(n);
- int d = (1 << l) / 2;
- int _cls = cnt = 0;
- for (int i = 0; i < n; i++) {
- int k = (p[i] - d + n) % n;
- a[c[k]].push_back(k);
- }
- for (int i = 0; i < cls; i++) {
- for (int j = 0; j < len(a[i]); j++) {
- if (j == 0 || c[(a[i][j] + d) % n] != c[(a[i][j - 1] + d) % n])
- _cls++;
- _c[a[i][j]] = _cls - 1;
- p[cnt++] = a[i][j];
- }
- }
- c = _c;
- cls = _cls;
- }
- lcp = calc_lcp(s, c, p);
- return vector<int>(p.begin() + 1, p.end());
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement