Advertisement
newb_ie

Suffix Array Implementation

Dec 9th, 2020 (edited)
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. /*
  2. ======================
  3. [     ___T_          ]
  4. [    | 6=6 | =>HI :-)]
  5. [    |__o__|         ]
  6. [ >===]__o[===<      ]
  7. [     [o__]          ]
  8. [      .".           ]
  9. [      |_|           ]
  10. [                    ]
  11. ======================
  12. */
  13.  
  14. #include<bits/stdc++.h>
  15. using namespace std;
  16.  
  17. int main () {
  18.      ios::sync_with_stdio(false);
  19.      cin.tie(nullptr);
  20.      cout.tie(nullptr);
  21.      int T = 1;
  22.      //~ cin >> T;
  23.      for (int test_case = 1; test_case <= T; ++test_case) {
  24.         string s;
  25.         cin >> s;
  26.         s += '$';
  27.         int n = (int) s.size();
  28.         pair<char,int> a_[n];
  29.         int p[n],c[n];
  30.         for (int i = 0; i < n; ++i) a_[i] = make_pair(s[i],i);
  31.         sort (a_,a_ + n);
  32.         for (int i = 0; i < n; ++i) p[i] = a_[i].second;
  33.         c[p[0]] = 0;
  34.         for (int i = 1; i < n; ++i) c[p[i]] = c[p[i - 1]] + (a_[i].first != a_[i - 1].first);
  35.         for (int k = 0; (1 << k) < n; ++k) {
  36.             pair<pair<int,int>,int> a[n];
  37.             for (int i = 0; i < n; ++i) a[i] = make_pair(make_pair(c[i],c[(i + (1 << k)) % n]),i);
  38.             sort (a,a + n);
  39.             for (int i = 0; i < n; ++i) p[i] = a[i].second;
  40.             c[p[0]] = 0;
  41.             for (int i = 1; i < n; ++i) c[p[i]] = c[p[i - 1]] + (a[i].first != a[i - 1].first);
  42.         }
  43.         for (int i = 0; i < n; ++i) cout << p[i] << " " << s.substr(p[i],n - p[i]) << "\n";
  44.      }
  45.      //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  46. }
  47.  
  48.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement