fork download 
  1.  
  2. vector<int> suffix_array(string s)
  3. {
  4.     int n = s.size();
  5.     vector<int> sa(n), rank(n);
  6.     for(int i = 0; i < n; i++)
  7.         rank[i] = s[i],
  8.         sa[i] = i;
  9.     for(int k = 0; k < n; k ? k *= 2 : k = 1)
  10.     {
  11.         stable_sort(sa.begin(), sa.end(), [&](int i, int j)
  12.              {
  13.                  if(rank[i] == rank[j])
  14.                     return rank[(i + k) % n] < rank[(j + k) % n];
  15.                  return rank[i] < rank[j];
  16.              });
  17.         vector<int> nrank(n);
  18.         int r = 0;
  19.         for(int i = 1; i < n; i++)
  20.         {
  21.             if(rank[sa[i]] != rank[sa[i - 1]]) r++;
  22.             else if(rank[(sa[i] + k) % n] != rank[(sa[i - 1] + k) % n]) r++;
  23.             nrank[sa[i]] = r;
  24.         }
  25.         rank = nrank;
  26.     }
  27.     return sa;
  28. }
  29.  
  30. vector<int> kasai(string s, vector<int> sa)
  31. {
  32.     int n = s.size(), k = 0;
  33.     vector<int> ra(n), lcp(n);
  34.     for(int i = 0; i < n; i++) ra[sa[i]] = i;
  35.     for(int i = 0; i < n; i++)
  36.     {
  37.         if(k) k--;
  38.         if(ra[i] == n - 1) {k = 0; continue;}
  39.         int j = sa[ra[i] + 1];
  40.         while(k < n && s[(i + k) % n] == s[(j + k) % n]) k++;
  41.         lcp[ra[i]] = k;
  42.         if(ra[(sa[ra[i]] + 1) % n] > ra[(sa[ra[j]] + 1) % n]) k = 0;
  43.     }
  44.     return lcp;
  45. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
prog.cpp:2:1: error: ‘vector’ does not name a type
 vector<int> suffix_array(string s)
 ^
prog.cpp:30:1: error: ‘vector’ does not name a type
 vector<int> kasai(string s, vector<int> sa)
 ^
stdout 
Standard output is empty
https://ideone.com/67rZRE
Suffix array O(n log^2 n)
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!