Advertisement
newb_ie

Number of Different string (Suffix Array)

Dec 16th, 2020
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 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> sorted[n];
  29.          int p[n],c[n];
  30.          for (int i = 0; i < n; ++i) sorted[i] = make_pair(s[i],i);
  31.          sort (sorted,sorted + n);
  32.          for (int i = 0; i < n; ++i) p[i] = sorted[i].second;
  33.          c[p[0]] = 0;
  34.          for (int i = 1; i < n; ++i) c[p[i]] = c[p[i - 1]] + (sorted[i].first != sorted[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.          int lcp[n];
  44.          int k = 0;
  45.          lcp[0] = 0;
  46.          for (int i = 0; i < n - 1; ++i) {
  47.              int pi = c[i];
  48.              int j = p[pi - 1];
  49.              while (s[i + k] == s[j + k]) ++k;
  50.              lcp[pi] = k;
  51.              k = max(k - 1,0);
  52.          }
  53.          int64_t sum = 0;
  54.          for (int i = 0; i < n; ++i) {
  55.              sum += (n - p[i]) - (lcp[i] + 1);
  56.          }
  57.          cout << sum << "\n";
  58.      }
  59.      //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  60. }
  61.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement