fork(1) download
copy 
  1.  
  2. vector<int> suffix_array(string s)
  3. {
  4.     int n = s.size(), N = n + 256;
  5.     vector<int> sa(n), ra(n);
  6.     for(int i = 0; i < n; i++) sa[i] = i, ra[i] = s[i];
  7.     for(int k = 0; k < n; k ? k *= 2 : k++)
  8.     {
  9.         vector<int> nsa(sa), nra(n), cnt(N);
  10.         for(int i = 0; i < n; i++) nsa[i] = (nsa[i] - k + n) % n;
  11.         for(int i = 0; i < n; i++) cnt[ra[i]]++;
  12.         for(int i = 1; i < N; i++) cnt[i] += cnt[i - 1];
  13.         for(int i = n - 1; i >= 0; i--) sa[--cnt[ra[nsa[i]]]] = nsa[i];
  14.  
  15.         int r = 0;
  16.         for(int i = 1; i < n; i++)
  17.         {
  18.             if(ra[sa[i]] != ra[sa[i - 1]]) r++;
  19.             else if(ra[(sa[i] + k) % n] != ra[(sa[i - 1] + k) % n]) r++;
  20.             nra[sa[i]] = r;
  21.         }
  22.         ra = nra;
  23.     }
  24.     return sa;
  25. }
  26.  
  27. vector<int> kasai(string s, vector<int> sa)
  28. {
  29.     int n = s.size(), k = 0;
  30.     vector<int> ra(n), lcp(n);
  31.     for(int i = 0; i < n; i++) ra[sa[i]] = i;
  32.     for(int i = 0; i < n; i++)
  33.     {
  34.         if(k) k--;
  35.         if(ra[i] == n - 1) {k = 0; continue;}
  36.         int j = sa[ra[i] + 1];
  37.         while(k < n && s[(i + k) % n] == s[(j + k) % n]) k++;
  38.         lcp[ra[i]] = k;
  39.         if(ra[(sa[ra[i]] + 1) % n] > ra[(sa[ra[j]] + 1) % n]) k = 0;
  40.     }
  41.     return lcp;
  42. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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:27:1: error: 'vector' does not name a type
 vector<int> kasai(string s, vector<int> sa)
 ^
stdout
copy 
Standard output is empty
https://ideone.com/4AsFVi
Suffix array O(n log 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!