fork download
copy 
  1. #include <bits/stdc++.h>
  2. #ifdef ONLINE_JUDGE
  3. #define endl "\n"
  4. #endif
  5. using namespace std;
  6. typedef long long LL;
  7. typedef vector<int> VI;
  8. typedef vector<VI> VVI;
  9. typedef pair<int, int> PII;
  10.  
  11. class SuffixArray {
  12.    public:
  13.     string s;
  14.     int n, __log_n;
  15.     vector<int> sa;            // Suffix Array
  16.     vector<vector<int>> ra;    // Rank Array
  17.     vector<vector<int>> _lcp;  // Longest Common Prefix
  18.     vector<int> __msb, __dollar;
  19.  
  20.     SuffixArray(string st) {
  21.         n = st.size();
  22.         __log_n = log2(n) + 1;
  23.         ra = vector<vector<int>>(__log_n, vector<int>(n));
  24.         sa = vector<int>(n);
  25.  
  26.         __msb = vector<int>(n);
  27.         int mx = -1;
  28.         for (int i = 0; i < n; i++) {
  29.             if (i >= (1 << (mx + 1)))
  30.                 mx++;
  31.             __msb[i] = mx;
  32.         }
  33.         this->s = st;
  34.         build_SA();
  35.     }
  36.  
  37.     void __counting_sort(int l, int k) {
  38.         int maxi = max(300, n);
  39.         vector<int> count(maxi, 0), temp_sa(n, 0);
  40.         for (int i = 0; i < n; i++) {
  41.             int idx = (i + k < n ? ra[l][i + k] : 0);
  42.             count[idx]++;
  43.         }
  44.         for (int i = 0, sum = 0; i < maxi; i++) {
  45.             int t = count[i];
  46.             count[i] = sum;
  47.             sum += t;
  48.         }
  49.         for (int i = 0; i < n; i++) {
  50.             int idx = sa[i] + k < n ? ra[l][sa[i] + k] : 0;
  51.             temp_sa[count[idx]++] = sa[i];
  52.         }
  53.         sa = temp_sa;
  54.     }
  55.  
  56.     void build_SA() {
  57.         for (int i = 0; i < n; i++)
  58.             ra[0][i] = s[i];
  59.         for (int i = 0; i < n; i++)
  60.             sa[i] = i;
  61.         for (int i = 0; i < __log_n - 1; i++) {
  62.             int k = (1 << i);
  63.             if (k >= n)
  64.                 break;
  65.             __counting_sort(i, k);
  66.             __counting_sort(i, 0);
  67.             int rank = 0;
  68.             ra[i + 1][sa[0]] = rank;
  69.             for (int j = 1; j < n; j++)
  70.                 if (ra[i][sa[j]] == ra[i][sa[j - 1]] &&
  71.                     ra[i][sa[j] + k] == ra[i][sa[j - 1] + k])
  72.                     ra[i + 1][sa[j]] = rank;
  73.                 else
  74.                     ra[i + 1][sa[j]] = ++rank;
  75.         }
  76.     }
  77.     void build_LCP() {
  78.         _lcp = vector<vector<int>>(__log_n, vector<int>(n));
  79.         for (int i = 0; i < n - 1; i++) {  // Build the LCP array in O(NlogN)
  80.             int x = sa[i], y = sa[i + 1], k, ret = 0;
  81.             for (k = __log_n - 1; k >= 0 && x < n && y < n; k--) {
  82.                 if ((1 << k) >= n)
  83.                     continue;
  84.                 if (ra[k][x] == ra[k][y])
  85.                     x += 1 << k, y += 1 << k, ret += 1 << k;
  86.             }
  87.             if (ret >= __dollar[sa[i]] - sa[i])
  88.                 ret = __dollar[sa[i]] - sa[i];
  89.             _lcp[0][i] = ret;  // LCP[i] shouldn’t exceed __dollar[sa[i]]
  90.         }  // __dollar[i] : index of __dollar to the right of i.
  91.         _lcp[0][n - 1] = 10 * n;
  92.         for (int i = 1; i < __log_n; i++) {  // O(1) RMQ structure in O(NlogN)
  93.             int add = (1 << (i - 1));
  94.             if (add >= n)
  95.                 break;  // small optimization
  96.             for (int j = 0; j < n; j++)
  97.                 if (j + add < n)
  98.                     _lcp[i][j] = min(_lcp[i - 1][j], _lcp[i - 1][j + add]);
  99.                 else
  100.                     _lcp[i][j] = _lcp[i - 1][j];
  101.         }
  102.     }
  103.  
  104.     int lcp(int x, int y) {
  105.         // O(1) LCP. x & y are indexes of the suffix in sa!
  106.         if (x == y)
  107.             return __dollar[sa[x]] - sa[x];
  108.         if (x > y)
  109.             swap(x, y);
  110.         y--;
  111.         int idx = __msb[y - x + 1], sub = (1 << idx);
  112.         return min(_lcp[idx][x], _lcp[idx][y - sub + 1]);
  113.     }
  114.  
  115.     bool equal(int i, int j, int p, int q) {
  116.         if (j - i != q - p)
  117.             return false;
  118.         int idx = __msb[j - i + 1], sub = (1 << idx);
  119.         return ra[idx][i] == ra[idx][p] &&
  120.                ra[idx][
  121. j - sub + 1] == ra[idx][q - sub + 1];
  122.     }  // Note : Do not forget to add a terminating ’$’
  123. };
  124.  
  125.  
  126. void solve() {
  127.     string s; cin >> s;
  128.     s += "$";
  129.     SuffixArray st(s);
  130.  
  131.     for (auto &x : st.sa) cout << x << " " << s.substr(x) << endl;
  132. }
  133.  
  134. int main() {
  135.     ios::sync_with_stdio(false);
  136.     cin.tie(nullptr);
  137.     cout.tie(nullptr);
  138.     // int t;cin >> t;while(t--)
  139.     solve();
  140.     return 0;
  141. }
  142.  
Success #stdin #stdout 0s 4540KB
comments (?)
stdin
copy 
bababa
stdout
copy 
6 $
5 a$
3 aba$
1 ababa$
4 ba$
0 bababa$
2 baba$
https://ideone.com/IdPWZ2
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!