SHARE
TWEET

Untitled

a guest Nov 12th, 2019 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define len(s) (s).size()
  3. using namespace std;
  4. const int ALPHABET = 256, n = 1e6;
  5.  
  6. int c[n], new_c[n], suf[n], new_suf[n], starts[n];
  7. void suffix_array(string s) {
  8.     s.push_back(0);
  9.     int n = len(s);
  10.     for (int i = 0; i < n; i++) {
  11.         suf[i] = i;
  12.         c[i] = s[i];
  13.         starts[s[i] + 1]++;
  14.     }
  15.     int sum = 0;
  16.     for (int i = 0; i < n; i++) {
  17.         sum += starts[i], starts[i] = sum;
  18.     }
  19.     for (int l = 0; l < n; l = (l ? 2 * l : 1)) {
  20.         for (int i = 0; i < n; i++) {
  21.             int pos = (suf[i] - l + n);
  22.             if (pos >= n) pos -= n;
  23.             new_suf[starts[c[pos]]++] = pos;
  24.         }
  25.         int type = -1;
  26.         long long last = -1;
  27.         for (int i = 0; i < n; i++) {
  28.             int v = new_suf[i];
  29.             if (last != (c[v] * 1ll * max(n, ALPHABET + 1) + c[(v + l) % n])) {
  30.                 last = (c[v] * 1ll * max(n, ALPHABET + 1) + c[(v + l) % n]);
  31.                 starts[++type] = i;
  32.             }
  33.             new_c[v] = type;
  34.         }
  35.         memcpy(new_c, c, sizeof c);
  36.         memcpy(new_suf, suf, sizeof suf);
  37.     }
  38. }
  39. signed main(){
  40.     ios::sync_with_stdio(0);
  41.     cin.tie(0);
  42.     string s;
  43.     cin >> s;
  44.     s += s;
  45.     s += s;
  46.     suffix_array(s);
  47. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top