Language: C++

#include <iostream>
#include <vector>
#include <bits/stdc++.h>

using namespace std;

int n , k;
int rank1[100010],rank2[100010];
int tmp[100010];

bool compare_sa(int i , int j){
  if(rank1[i] != rank1[j]) return rank1[i] < rank1[j];
  else{
    int ri = i + k <= n ? rank1[i+k] : -1;
    int rj = j + k <= n ? rank1[j+k] ; -1;
    return ri < rj;
  }
}

void construct_sa(string S , int sa){
  n = S.length();
  
  for(int i=0;i<=n;i++){
    sa[i] = i;
    rank1[i] = i < n ? S[i] : -1;
  }
  
  for(k=1;k<=n;k*=2){
    sort(sa, sa+n+1,compare_sa);
    
    tmp[sa[0]] = 0;
    for(int i=1;i<=n;i++){
      tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
    }
    for(int i = 0;i<=n;i++){
      rank[i] = tmp[i];
    }
  }
}

void construct_lcp(string S ,int sa , int lcp){
  int m = S.length();
  for(int i=0;i<=m;i++) rank2[sa[i]] = i;
  
  int h = 0;
  lcp[0] = 0;
  for(int i=0;i<m;i++){
    int j = sa[rank2[i]-1];
    
    if(h>0) h--;
    for(; j+h<n && i+h<n;h++){
      if(S[j+h] != S[i+h]) break;
    }
    
    lcp[rank2[i] - 1] = h;
  }
}

string s;
int sa[100010],lcp[100010];


int main(){
  int ss = s.size();
  
  construct_sa(s,sa);
  construct_lcp(s,sa,lcp);
  
  int ans = 0;
  for(int i=0;i< s.size();i++){
    if((sa[i] < ss) != (sa[i+1] < ss )){
      ans = max(ans , lcp[i]);
    }
  }
  cout << ans << endl;
}
    


Compiler output:
a.cc: In function 'bool compare_sa(int, int)':
a.cc:15:37: error: expected ':' before ';' token
   15 |     int rj = j + k <= n ? rank1[j+k] ; -1;
      |                                     ^~
      |                                     :
a.cc:15:38: error: expected primary-expression before ';' token
   15 |     int rj = j + k <= n ? rank1[j+k] ; -1;
      |                                      ^
a.cc: In function 'void construct_sa(std::string, int)':
a.cc:24:7: error: invalid types 'int[int]' for array subscript
   24 |     sa[i] = i;
      |       ^
a.cc:31:11: error: invalid types 'int[int]' for array subscript
   31 |     tmp[sa[0]] = 0;
      |           ^
a.cc:33:13: error: invalid types 'int[int]' for array subscript
   33 |       tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
      |             ^
a.cc:33:26: error: invalid types 'int[int]' for array subscript
   33 |       tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
      |                          ^
a.cc:33:49: error: invalid types 'int[int]' for array subscript
   33 |       tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
      |                                                 ^
a.cc:33:58: error: invalid types 'int[int]' for array subscript
   33 |       tmp[sa[i]] = tmp[sa[i-1]] + (compare_sa(sa[i-1], sa[i]) ? 1 : 0);
      |                                                          ^
a.cc:36:12: error: redeclaration of 'auto i'
   36 |       rank[i] = tmp[i];
      |            ^
a.cc:35:13: note: 'int i' previously declared here
   35 |     for(int i = 0;i<=n;i++){
      |             ^
a.cc:36:21: error: use of 'i' before deduction of 'auto'
   36 |       rank[i] = tmp[i];
      |                     ^
a.cc: In function 'void construct_lcp(std::string, int, int)':
a.cc:43:33: error: invalid types 'int[int]' for array subscript
   43 |   for(int i=0;i<=m;i++) rank2[sa[i]] = i;
      |                                 ^
a.cc:46:6: error: invalid types 'int[int]' for array subscript
   46 |   lcp[0] = 0;
      |      ^
a.cc:48:15: error: invalid types 'int[int]' for array subscript
   48 |     int j = sa[rank2[i]-1];
      |               ^
a.cc:55:8: error: invalid types 'int[int]' for array subscript
   55 |     lcp[rank2[i] - 1] = h;
      |        ^
a.cc: In function 'int main()':
a.cc:66:18: error: invalid conversion from 'int*' to 'int' [-fpermissive]
   66 |   construct_sa(s,sa);
      |                  ^~
      |                  |
      |                  int*
a.cc:20:34: note:   initializing argument 2 of 'void construct_sa(std::string, int)'
   20 | void construct_sa(string S , int sa){
      |                              ~~~~^~
a.cc:67:19: error: invalid conversion from 'int*' to 'int' [-fpermissive]
   67 |   construct_lcp(s,sa,lcp);
      |                   ^~
      |                   |
      |                   int*
a.cc:41:34: note:   initializing argument 2 of 'void construct_lcp(std::string, int, int)'
   41 | void construct_lcp(string S ,int sa , int lcp){
      |                              ~~~~^~
a.cc:67:22: error: invalid conversion from 'int*' to 'int' [-fpermissive]
   67 |   construct_lcp(s,sa,lcp);
      |                      ^~~
      |                      |
      |                      int*
a.cc:41:43: note:   initializing argument 3 of 'void construct_lcp(std::string, int, int)'
   41 | void construct_lcp(string S ,int sa , int lcp){
      |                                       ~~~~^~~
In file included from /usr/include/c++/14/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:3:
/usr/include/c++/14/bits/stl_algo.h: In instantiation of 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]':
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int; _Compare = bool (*)(int, int)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:29:9:   required from here
   29 |     sort(sa, sa+n+1,compare_sa);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1780:17: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
 1780 |                 __val = _GLIBCXX_MOVE(*__i);
      |                 ^~~~~
In file included from /usr/include/c++/14/bits/exception_ptr.h:41,
                 from /usr/include/c++/14/exception:166,
                 from /usr/include/c++/14/ios:41,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algo.h:1780:25: error: invalid type argument of unary '*' (have 'int')
 1780 |                 __val = _GLIBCXX_MOVE(*__i);
      |                         ^~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1782:15: error: invalid type argument of unary '*' (have 'int')
 1782 |               *__first = _GLIBCXX_MOVE(__val);
      |               ^~~~~~~~
In file included from /usr/include/c++/14/bits/stl_algobase.h:71,
                 from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44:
/usr/include/c++/14/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = int; _Iterator2 = int; _Compare = bool (*)(int, int)]':
/usr/include/c++/14/bits/stl_algo.h:1777:14:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1777 |           if (__comp(__i, __first))
      |               ~~~~~~^~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1817:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1817 |           std::__insertion_sort(__first, __first + int(_S_threshold), __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1908:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1908 |           std::__final_insertion_sort(__first, __last, __comp);
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:4805:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int; _Compare = bool (*)(int, int)]'
 4805 |       std::__sort(__first, __last, __gnu_cxx::__ops::__iter_comp_iter(__comp));
      |       ~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:29:9:   required from here
   29 |     sort(sa, sa+n+1,compare_sa);
      |     ~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:31: error: invalid type argument of unary '*' (have 'int')
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                               ^~~~~~
/usr/include/c++/14/bits/predefined_ops.h:158:39: error: invalid type argument of unary '*' (have 'int')
  158 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                                       ^~~~~~
In file included from /usr/include/c++/14/bits/stl_algo.h:61:
/usr/include/c++/14/bits/stl_heap.h: In instantiation of 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]':
/usr/include/c++/14/bits/stl_algo.h:1593:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1593 |       std::__make_heap(__first, __middle, __comp);
      |       ~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1868:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1868 |       std::__heap_select(__first, __middle, __last, __comp);
      |       ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1884:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int; _Size = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<bool (*)(int, int)>]'
 1884 |               std::__partial_sort(__first, __last, __last, __comp);
      |               ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algo.h:1905:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator,