fork download 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void *wmem;
  5. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  6.   static int skip[16]={0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  7.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  8.   (*arr)=(T*)(*mem);
  9.   (*mem)=((*arr)+x);
  10. }
  11. template<class T> void SuffixArray(T *s, int N, int K, int *SA, int *LCP = NULL, void *mem = wmem){
  12.   char *lms, *t;
  13.   int *cnt, *cnt1, *cnt2, d, i, j, m, name, pos, prev, *s1;
  14.   walloc1d(&t, N+1, &mem);
  15.   walloc1d(&lms, N+1, &mem);
  16.   walloc1d(&cnt, K+1, &mem);
  17.   walloc1d(&cnt1, K+1, &mem);
  18.   walloc1d(&cnt2, K+1, &mem);
  19.   N++;
  20.   s[N-1] = 0;
  21.   t[N-1] = 1;
  22.   t[N-2] = 0;
  23.   for(i=N-3;i>=0;i--){
  24.     if(s[i] < s[i+1] || (s[i]==s[i+1] && t[i+1])){
  25.       t[i] = 1;
  26.     }
  27.     else{
  28.       t[i] = 0;
  29.     }
  30.   }
  31.   lms[0] = 0;
  32.   for(i=(1);i<(N);i++){
  33.     if(t[i] && !t[i-1]){
  34.       lms[i] = 1;
  35.     }
  36.     else{
  37.       lms[i] = 0;
  38.     }
  39.   }
  40.   for(i=0;i<(K+1);i++){
  41.     cnt1[i] = 0;
  42.   }
  43.   for(i=0;i<(N);i++){
  44.     cnt1[s[i]]++;
  45.   }
  46.   j = 0;
  47.   for(i=0;i<(K+1);i++){
  48.     j += cnt1[i];
  49.     cnt2[i] = j - cnt1[i];
  50.     cnt1[i] = j;
  51.   }
  52.   for(i=0;i<(K+1);i++){
  53.     cnt[i] = cnt1[i];
  54.   }
  55.   for(i=0; i<N; i++){
  56.     SA[i] = -1;
  57.   }
  58.   for(i=1; i<N; i++){
  59.     if(lms[i]){
  60.       SA[--cnt[s[i]]]=i;
  61.     }
  62.   }
  63.   for(i=0;i<(K+1);i++){
  64.     cnt[i] = cnt2[i];
  65.   }
  66.   for(i=0;i<(N);i++){
  67.     j = SA[i]-1;
  68.     if(j>=0 && !t[j]){
  69.       SA[cnt[s[j]]++] = j;
  70.     }
  71.   }
  72.   for(i=0;i<(K+1);i++){
  73.     cnt[i] = cnt1[i];
  74.   }
  75.   for(i=N-1;i>=0;i--){
  76.     j = SA[i] - 1;
  77.     if(j>=0 && t[j]){
  78.       SA[--cnt[s[j]]] = j;
  79.     }
  80.   }
  81.   m = 0;
  82.   for(i=0;i<(N);i++){
  83.     if(lms[SA[i]]){
  84.       SA[m++] = SA[i];
  85.     }
  86.   }
  87.   for(i=(m);i<(N);i++){
  88.     SA[i] = -1;
  89.   }
  90.   name=0;
  91.   prev=-1;
  92.   for(i=0;i<(m);i++){
  93.     pos = SA[i];
  94.     for(d=0;d<(N);d++){
  95.       if(prev==-1 || s[pos+d]!=s[prev+d] || t[pos+d]!=t[prev+d]){
  96.         name++;
  97.         prev=pos;
  98.         break;
  99.       }
  100.       else if(d>0 && (lms[pos+d] || lms[prev+d])){
  101.         break;
  102.       }
  103.     }
  104.     pos /= 2;
  105.     SA[m+pos]=name-1;
  106.   }
  107.   for(i=N-1, j=N-1; i>=m; i--){
  108.     if(SA[i]>=0){
  109.       SA[j--]=SA[i];
  110.     }
  111.   }
  112.   s1 = SA+N-m;
  113.   if(name<m){
  114.     SuffixArray(s1, m-1, name-1, SA, NULL, mem);
  115.   }
  116.   else{
  117.     for(i=0; i<m; i++){
  118.       SA[s1[i]] = i;
  119.     }
  120.   }
  121.   for(i=0;i<(K+1);i++){
  122.     cnt[i] = cnt1[i];
  123.   }
  124.   for(i=1, j=0; i<N; i++){
  125.     if(lms[i]){
  126.       s1[j++]=i;
  127.     }
  128.   }
  129.   for(i=0; i<m; i++){
  130.     SA[i]=s1[SA[i]];
  131.   }
  132.   for(i=m; i<N; i++){
  133.     SA[i]=-1;
  134.   }
  135.   for(i=m-1; i>=0; i--){
  136.     j=SA[i];
  137.     SA[i]=-1;
  138.     SA[--cnt[s[j]]]=j;
  139.   }
  140.   for(i=0;i<(N);i++){
  141.     j = SA[i]-1;
  142.     if(j>=0 && !t[j]){
  143.       SA[cnt2[s[j]]++] = j;
  144.     }
  145.   }
  146.   for(i=N-1;i>=0;i--){
  147.     j = SA[i] - 1;
  148.     if(j>=0 && t[j]){
  149.       SA[--cnt1[s[j]]] = j;
  150.     }
  151.   }
  152.   if(LCP != NULL){
  153.     cnt = (int*)t;
  154.     d = 0;
  155.     for(i=0;i<(N);i++){
  156.       cnt[SA[i]] = i;
  157.     }
  158.     for(i=0;i<(N);i++){
  159.       if(cnt[i]){
  160.         for(j=SA[cnt[i]-1]; j+d<N-1&&i+d<N-1&&s[j+d]==s[i+d];d++){
  161.           ;
  162.         }
  163.         LCP[cnt[i]]=d;
  164.       }
  165.       else{
  166.         LCP[cnt[i]] = -1;
  167.       }
  168.       if(d>0){
  169.         d--;
  170.       }
  171.     }
  172.   }
  173. }
  174. char memarr[96000000];
  175. #define main dummy_main
  176. int main(){
  177.   wmem = memarr;
  178.   return 0;
  179. }
  180. #undef main
  181. char S[100001];
  182. int SA[100001];
  183. class Solution{
  184.   public:
  185.   string lastSubstring(string s){
  186.     int N, i;
  187.     dummy_main();
  188.     N = s.size();
  189.     for(i=0;i<(N);i++){
  190.       S[i] = s[i];
  191.     }
  192.     SuffixArray(S, N, 128, SA);
  193.     return s.substr(SA[N]);
  194.   }
  195. }
  196. ;
  197. // cLay varsion 20190820-1
  198.  
  199. // --- original code ---
  200. // #define main dummy_main
  201. // {}
  202. // #undef main
  203. // 
  204. // char S[100001];
  205. // int SA[100001];
  206. // 
  207. // class Solution {
  208. // public:
  209. //   string lastSubstring(string s) {
  210. //     dummy_main();
  211. // 
  212. //     int N;
  213. //     N = s.size();
  214. //     rep(i,N) S[i] = s[i];
  215. //     SuffixArray(S, N, 128, SA);
  216. //     return s.substr(SA[N]);
  217. //   }
  218. // };
  219.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout 
Standard output is empty
https://ideone.com/40P4Cr
language:
C++14 (gcc 8.3)
created:
6 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!