fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MX = 1e4 + 10;
  5. int SR[14][MX], LCP[MX];
  6. char text[MX];
  7.  
  8. struct myTuple{ int fir, sec, idx; };
  9. myTuple SA[MX];
  10.  
  11. bool cmp(myTuple a, myTuple b){
  12.  return (a.fir == b.fir) ? a.sec < b.sec :  a.fir < b.fir;
  13. }
  14.  
  15. void build_SA(){
  16.  memset(SR, 0, sizeof(SR));
  17.  int N = strlen(text);
  18.  for(int i = 0; i<N; i++) SR[0][i] = text[i] - 'a';
  19.  
  20.  for(int cnt = 1, stp = 1; cnt < N; cnt <<= 1, stp++){
  21.   for(int i = 0; i < N; i++){
  22.    SA[i].fir = SR[stp - 1][i];
  23.    SA[i].sec = (i + cnt) < N ? SR[stp - 1][i + cnt] : -1;
  24.    SA[i].idx = i;
  25.   }
  26.   sort(SA, SA + N, cmp);
  27.   SR[stp][SA[0].idx] = 0;
  28.   for(int i = 1, cr = 0; i < N; i++){
  29.    if(SA[i - 1].fir != SA[i].fir || SA[i - 1].sec != SA[i].sec) cr++;
  30.    SR[stp][SA[i].idx] = cr;
  31.   }
  32.  }
  33. }
  34.  
  35. void build_LCP(){
  36.  memset(LCP, 0, sizeof(LCP));
  37.  int N = strlen(text), mx = 0;
  38.  
  39.  for(int i = 1; i<N; i++){
  40.   int i1 = SA[i - 1].idx;
  41.   int i2 = SA[i].idx;
  42.  
  43.   for(int j = 13; j >= 0; j--){
  44.    if(SR[j][i1] == SR[j][i2] && SR[j][i2]){
  45.     LCP[i] += (1 << j);
  46.     i1 += (1 << j);
  47.     i2 += (1 << j);
  48.    }
  49.   }
  50.   mx = max(mx, LCP[i]);
  51.  }
  52.  printf("%d\n", mx);
  53. }
  54.  
  55.  
  56. int main() {
  57.  int t;
  58.  scanf("%d", &t);
  59.  for(int i = 1; i <= t; i++){
  60.   memset(text, 0, sizeof(text));
  61.   scanf("%s", text);
  62.   int N = strlen(text);
  63.   text[N] = '$';
  64.   build_SA();
  65.   build_LCP();
  66.  }
  67.  return 0;
  68. }
Success #stdin #stdout 0s 4188KB
comments (?)
stdin
copy 
3
abcdefghikjlmn
abcabcabc
abcdabcabb
stdout
copy 
0
6
3
https://ideone.com/bLGTpc
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
public

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!