fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define f first
  4. #define s second
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8.  
  9. using namespace std;
  10.  
  11. const int N = 1e5 + 10;
  12. const int L = 20;
  13.  
  14. char s[N];
  15. int n, lg;
  16. int p[L][N], suf[N], lcp[N];
  17. pair<pair<int, int>, int> t[N];
  18.  
  19. void order(int j){
  20.     sort(t, t + n);
  21.     for(int i = 0; i < n; i++){
  22.         p[j][t[i].s] = i;
  23.         if(i > 0 && t[i].f == t[i - 1].f){
  24.             p[j][t[i].s] = p[j][t[i - 1].s];
  25.         }
  26.     }
  27. }
  28.  
  29. void build(){
  30.     for(lg = 0; lg == 0 || 1 << (lg - 1) < n; lg++){
  31.         for(int i = 0; i < n; i++){
  32.             if(lg == 0){
  33.                 t[i] = {{s[i], -1}, i}; continue;
  34.             }
  35.             int cnt = 1 << (lg - 1);
  36.             t[i] = {{p[lg - 1][i], -1}, i};
  37.             if(i + cnt < n) t[i].f.s = p[lg - 1][i + cnt];
  38.         }
  39.         order(lg);
  40.     }
  41.     lg--;
  42.     for(int i = 0; i < n; i++) suf[p[lg][i]] = i;
  43. }
  44.  
  45. int main(){
  46.     ios::sync_with_stdio(0);
  47.     cin.tie(0);
  48.  
  49.     scanf("%s", s);
  50.     n = strlen(s);
  51.  
  52.     build();
  53.  
  54.     int k = 0;
  55.     for(int i = 0; i < n; i++){
  56.         if(p[lg][i] == n - 1){
  57.             k = 0; continue;
  58.         }
  59.         int j = suf[p[lg][i] + 1];
  60.         while(i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
  61.         lcp[p[lg][i]] = k;
  62.         if(k > 0) k--;
  63.     }
  64.  
  65.     int len = * max_element(lcp, lcp + n - 1);
  66.     int ind = max_element(lcp, lcp + n - 1) - lcp;
  67.  
  68.     for(int i = 0; i < len; i++){
  69.         printf("%c", s[suf[ind] + i]);
  70.     }
  71.     printf("\n");
  72.  
  73.  
  74.  
  75.  
  76.  
  77.     return 0;
  78. }
Success #stdin #stdout 0s 4256KB
comments (?)
stdin
copy 
abcefgabc
stdout
copy 
abc
https://ideone.com/7v8Fb3
language:
C++14 (gcc 8.3)
created:
3 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!