fork download
copy 
  1. #pragma GCC optimize ("Ofast")
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void *wmem;
  5. char memarr[96000000];
  6. template<class T> inline void walloc1d(T **arr, int x, void **mem = &wmem){
  7.   static int skip[16] = {0, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
  8.   (*mem) = (void*)( ((char*)(*mem)) + skip[((unsigned long long)(*mem)) & 15] );
  9.   (*arr)=(T*)(*mem);
  10.   (*mem)=((*arr)+x);
  11. }
  12. template<class S, class T> inline S chmin(S &a, T b){
  13.   if(a>b){
  14.     a=b;
  15.   }
  16.   return a;
  17. }
  18. template<class T> void SuffixArray(T *s, int N, int K, int *SA, int *LCP = NULL, void *mem = wmem){
  19.   int i;
  20.   int j;
  21.   int d;
  22.   int m;
  23.   int *s1;
  24.   int name;
  25.   int prev;
  26.   int pos;
  27.   char *t;
  28.   char *lms;
  29.   int *cnt;
  30.   int *cnt1;
  31.   int *cnt2;
  32.   walloc1d(&t, N+1, &mem);
  33.   walloc1d(&lms, N+1, &mem);
  34.   walloc1d(&cnt, K+1, &mem);
  35.   walloc1d(&cnt1, K+1, &mem);
  36.   walloc1d(&cnt2, K+1, &mem);
  37.   N++;
  38.   s[N-1] = 0;
  39.   t[N-1] = 1;
  40.   t[N-2] = 0;
  41.   for(i=N-3;i>=0;i--){
  42.     if(s[i] < s[i+1] || (s[i]==s[i+1] && t[i+1])){
  43.       t[i] = 1;
  44.     }
  45.     else{
  46.       t[i] = 0;
  47.     }
  48.   }
  49.   lms[0] = 0;
  50.   int tU__gIr_ = N;
  51.   for(i=(1);i<(tU__gIr_);i++){
  52.     if(t[i] && !t[i-1]){
  53.       lms[i] = 1;
  54.     }
  55.     else{
  56.       lms[i] = 0;
  57.     }
  58.   }
  59.   for(i=(0);i<(K+1);i++){
  60.     cnt1[i] = 0;
  61.   }
  62.   for(i=(0);i<(N);i++){
  63.     cnt1[s[i]]++;
  64.   }
  65.   j = 0;
  66.   for(i=(0);i<(K+1);i++){
  67.     j += cnt1[i];
  68.     cnt2[i] = j - cnt1[i];
  69.     cnt1[i] = j;
  70.   }
  71.   for(i=(0);i<(K+1);i++){
  72.     cnt[i] = cnt1[i];
  73.   }
  74.   for(i=0; i<N; i++){
  75.     SA[i] = -1;
  76.   }
  77.   for(i=1; i<N; i++){
  78.     if(lms[i]){
  79.       SA[--cnt[s[i]]]=i;
  80.     }
  81.   }
  82.   for(i=(0);i<(K+1);i++){
  83.     cnt[i] = cnt2[i];
  84.   }
  85.   for(i=(0);i<(N);i++){
  86.     j = SA[i]-1;
  87.     if(j>=0 && !t[j]){
  88.       SA[cnt[s[j]]++] = j;
  89.     }
  90.   }
  91.   for(i=(0);i<(K+1);i++){
  92.     cnt[i] = cnt1[i];
  93.   }
  94.   for(i=N-1;i>=0;i--){
  95.     j = SA[i] - 1;
  96.     if(j>=0 && t[j]){
  97.       SA[--cnt[s[j]]] = j;
  98.     }
  99.   }
  100.   m = 0;
  101.   for(i=(0);i<(N);i++){
  102.     if(lms[SA[i]]){
  103.       SA[m++] = SA[i];
  104.     }
  105.   }
  106.   int H31bcJ8S = N;
  107.   for(i=(m);i<(H31bcJ8S);i++){
  108.     SA[i] = -1;
  109.   }
  110.   name=0;
  111.   prev=-1;
  112.   for(i=(0);i<(m);i++){
  113.     pos = SA[i];
  114.     for(d=(0);d<(N);d++){
  115.       if(prev==-1 || s[pos+d]!=s[prev+d] || t[pos+d]!=t[prev+d]){
  116.         name++;
  117.         prev=pos;
  118.         break;
  119.       }
  120.       else if(d>0 && (lms[pos+d] || lms[prev+d])){
  121.         break;
  122.       }
  123.     }
  124.     pos /= 2;
  125.     SA[m+pos]=name-1;
  126.   }
  127.   for(i=N-1, j=N-1; i>=m; i--){
  128.     if(SA[i]>=0){
  129.       SA[j--]=SA[i];
  130.     }
  131.   }
  132.   s1 = SA+N-m;
  133.   if(name<m){
  134.     SuffixArray(s1, m-1, name-1, SA, NULL, mem);
  135.   }
  136.   else{
  137.     for(i=0; i<m; i++){
  138.       SA[s1[i]] = i;
  139.     }
  140.   }
  141.   for(i=(0);i<(K+1);i++){
  142.     cnt[i] = cnt1[i];
  143.   }
  144.   for(i=1, j=0; i<N; i++){
  145.     if(lms[i]){
  146.       s1[j++]=i;
  147.     }
  148.   }
  149.   for(i=0; i<m; i++){
  150.     SA[i]=s1[SA[i]];
  151.   }
  152.   for(i=m; i<N; i++){
  153.     SA[i]=-1;
  154.   }
  155.   for(i=m-1; i>=0; i--){
  156.     j=SA[i];
  157.     SA[i]=-1;
  158.     SA[--cnt[s[j]]]=j;
  159.   }
  160.   for(i=(0);i<(N);i++){
  161.     j = SA[i]-1;
  162.     if(j>=0 && !t[j]){
  163.       SA[cnt2[s[j]]++] = j;
  164.     }
  165.   }
  166.   for(i=N-1;i>=0;i--){
  167.     j = SA[i] - 1;
  168.     if(j>=0 && t[j]){
  169.       SA[--cnt1[s[j]]] = j;
  170.     }
  171.   }
  172.   if(LCP != NULL){
  173.     cnt = (int*)t;
  174.     d = 0;
  175.     for(i=(0);i<(N);i++){
  176.       cnt[SA[i]] = i;
  177.     }
  178.     for(i=(0);i<(N);i++){
  179.       if(cnt[i]){
  180.         for(j=SA[cnt[i]-1]; j+d<N-1&&i+d<N-1&&s[j+d]==s[i+d];d++){
  181.           ;
  182.         }
  183.         LCP[cnt[i]]=d;
  184.       }
  185.       else{
  186.         LCP[cnt[i]] = -1;
  187.       }
  188.       if(d>0){
  189.         d--;
  190.       }
  191.     }
  192.   }
  193. }
  194. #define main dummy_main
  195. int main(){
  196.   wmem = memarr;
  197.   return 0;
  198. }
  199. #undef main
  200. int A[2002];
  201. int ok[2002];
  202. int SA[2002];
  203. int LCP[2002];
  204. class Solution{
  205.   public:
  206.   int distinctEchoSubstrings(string str){
  207.     int i;
  208.     dummy_main();
  209.     int res = 0;
  210.     int N = str.size();
  211.     int k;
  212.     int len;
  213.     for(i=(0);i<(N);i++){
  214.       A[i] = str[i]-'a'+1;
  215.     }
  216.     SuffixArray(A,N,128,SA,LCP);
  217.     for(i=(0);i<(N+1);i++){
  218.       ok[i] = 0;
  219.     }
  220.     for(i=(1);i<(N+1);i++){
  221.       int j;
  222.       for(j=(LCP[i]+1);j<(N+1);j++){
  223.         ok[j] = 1;
  224.       }
  225.       len = 1073709056;
  226.       for(j=(i+1);j<(N+1);j++){
  227.         chmin(len, LCP[j]);
  228.         k = abs(SA[i]-SA[j]);
  229.         if(k <= len){
  230.           res += ok[k];
  231.           ok[k] = 0;
  232.         }
  233.       }
  234.     }
  235.     return res;
  236.   }
  237. }
  238. ;
  239. // cLay varsion 20200112-1
  240.  
  241. // --- original code ---
  242. // #define main dummy_main
  243. // {}
  244. // #undef main
  245. // 
  246. // int A[2002];
  247. // int ok[2002];
  248. // int SA[2002], LCP[2002];
  249. // 
  250. // class Solution {
  251. // public:
  252. //   int distinctEchoSubstrings(string str) {
  253. //     dummy_main();
  254. // 
  255. //     int res = 0;
  256. //     int N = str.size();
  257. //     int k, len;
  258. // 
  259. //     rep(i,N) A[i] = str[i]-'a'+1;
  260. //     SuffixArray(A,N,128,SA,LCP);
  261. // 
  262. //     rep(i,N+1) ok[i] = 0;
  263. //     rep(i,1,N+1){
  264. //       rep(j,LCP[i]+1,N+1) ok[j] = 1;
  265. //       len = int_inf;
  266. //       rep(j,i+1,N+1){
  267. //         len <?= LCP[j];
  268. //         k = abs(SA[i]-SA[j]);
  269. //         if(k <= len) res += ok[k], ok[k] = 0;
  270. //       }
  271. //     }
  272. // 
  273. //     return res;
  274. //   }
  275. // };
  276.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
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
copy 
Standard output is empty
https://ideone.com/C1lpP3
language:
C++14 (gcc 8.3)
created:
4 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!