，这里面输出方案的部分复杂度我不会证，而且觉得很假，我肯定95%写这种的人都是抄的而且不会证复杂度。。。。

输出方案的代码参考黄学长的

还有就是论文，有下载链接

记得特判长度是1的情况

关于输出方案

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int N = 1e5 + 7;typedef pair
           
             pii;vector
            
             qq;int T, n, st[N][17];struct SA { int k, sa[N], rnk[N], H[N], st[N][17]; char s[N]; bool cmp(int *y, int a, int b, int m) {return y[a] == y[b] && y[a + m] == y[b + m];} void Sort(int *x, int *y, int *rk) { static int C[N]; for (int i = 0; i <= k; ++i) C[i] = 0; for (int i = 1; i <= n; ++i) ++C[rk[i]]; for (int i = 1; i <= k; ++i) C[i] += C[i - 1]; for (int i = n; i; --i) y[C[rk[x[i]]]--] = x[i]; } void get_SA() { static int Y[N]; int *y = Y, *rk = rnk; k = 128; for (int i = 1; i <= n; ++i) rk[i] = s[y[i] = i]; Sort(y, sa, rk); for (int m = 1, p = 0; p < n; k = p, m <<= 1) { for (p = 0; p < m; ++p) y[p + 1] = n - m + p + 1; for (int i = 1; i <= n; ++i) if (sa[i] > m) y[++p] = sa[i] - m; Sort(y, sa, rk), swap(rk, y); rk[sa[p = 1]] = 1; for (int i = 2; i <= n; ++i) rk[sa[i]] = cmp(y, sa[i], sa[i - 1], m) ? p : ++p; } for (int i = 1; i <= n; ++i) rnk[sa[i]] = i, Y[i] = 0; } void get_H() { for (int i = 1, k = 0; i <= n; H[rnk[i++]] = k) for (k ? --k : 0; s[i + k] == s[sa[rnk[i] - 1] + k]; ++k); for (int i = 2; i <= n; ++i) st[i][0] = H[i]; for (int j = 1; j <= __lg(n); ++j) for (int i = 2; i + (1 << j) - 1 <= n; ++i) st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); } void clear() { fill(rnk + 1, rnk + 1 + n, 0); } int lcp(int x, int y) { if (x == y) return n - x + 1; x = rnk[x], y = rnk[y]; if (x > y) swap(x, y); ++x; int k = __lg(y - x + 1); return min(st[x][k], st[y - (1 << k) + 1][k]); }} a, b;inline bool chmax(int &x, int y) {return x < y ? x = y, 1 : 0;}inline bool chmin(int &x, int y) {return x > y ? x = y, 1 : 0;}inline int Min(int l, int r) { int k = __lg(r - l + 1); return min(st[l][k], st[r - (1 << k) + 1][k]);}int main() { while (~scanf("%s", a.s + 1) && a.s[1] != '#') { int ans = 1, ansl, ansrk = 1e9, Len; n = strlen(a.s + 1); for (int i = 1; i <= n; ++i) b.s[i] = a.s[n - i + 1]; b.s[n + 1] = a.s[n + 1] = 0; a.get_SA(), a.get_H(), b.get_SA(), b.get_H(); for (int i = 1; i <= n; ++i) st[i][0] = a.rnk[i]; for (int j = 1; j <= __lg(n); ++j) for (int i = 1; i + (1 << j) - 1 <= n; ++i) st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]); for (int len = 1; len <= n; ++len) for (int i = 1; i + len <= n; i += len) { int LCP = a.lcp(i, i + len), LCS = b.lcp(n - i + 1, n - i - len + 1), tmp; if (chmax(ans, tmp = (LCP + LCS - 1 + len) / len)) ansrk = 1e9; if (tmp == ans) { int l = i - LCS + 1, res = (LCP + LCS - 1 + len) % len; if (chmin(ansrk, Min(l, l + res))) ansl = a.sa[ansrk], Len = len; } } static int cnt = 0; printf("Case %d: ", ++cnt); if (ans == 1) putchar(*min_element(a.s + 1, a.s + 1 + n)); else for (int i = 0; i < ans * Len; ++i) putchar(a.s[ansl + i]); puts(""); a.clear(), b.clear(); } return 0;}
            
           
          
         
        
       
      
     
    

#include 
    
     using namespace std;const int N = 5e4 + 7;int T, n;struct SA {  int k, sa[N], rnk[N], H[N], st[N][17];  char s[N];  bool cmp(int *y, int a, int b, int m) {return y[a] == y[b] && y[a + m] == y[b + m];}  void Sort(int *x, int *y, int *rk) {    static int C[N];    for (int i = 0; i <= k; ++i) C[i] = 0;    for (int i = 1; i <= n; ++i) ++C[rk[i]];    for (int i = 1; i <= k; ++i) C[i] += C[i - 1];    for (int i = n; i; --i) y[C[rk[x[i]]]--] = x[i];  }  void get_SA() {    static int Y[N];    int *y = Y, *rk = rnk;    k = 128;    for (int i = 1; i <= n; ++i) rk[i] = s[y[i] = i];    Sort(y, sa, rk);    for (int m = 1, p = 0; p < n; k = p, m <<= 1) {      for (p = 0; p < m; ++p) y[p + 1] = n - m + p + 1;      for (int i = 1; i <= n; ++i) if (sa[i] > m) y[++p] = sa[i] - m;      Sort(y, sa, rk), swap(rk, y);      rk[sa[p = 1]] = 1;      for (int i = 2; i <= n; ++i) rk[sa[i]] = cmp(y, sa[i], sa[i - 1], m) ? p : ++p;    }    for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;  }  void get_H() {    for (int i = 1, k = 0; i <= n; H[rnk[i++]] = k)      for (k ? --k : 0; s[i + k] == s[sa[rnk[i] - 1] + k]; ++k);    for (int i = 2; i <= n; ++i) st[i][0] = H[i];    for (int j = 1; j <= __lg(n); ++j)      for (int i = 2; i + (1 << j) - 1 <= n; ++i) st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);  }  int lcp(int x, int y) {    x = rnk[x], y = rnk[y];    if (x > y) swap(x, y);    ++x;    int k = __lg(y - x + 1);    return min(st[x][k], st[y - (1 << k) + 1][k]);  }} a, b;inline int gi() {int c = getchar(); while (!isalpha(c)) c = getchar(); return c;}inline void chmax(int &x, int y) {if (x < y) x = y;}int main() {  cin >> T;  while (T--) {    cin >> n;    for (int i = 1; i <= n; ++i) a.s[i] = gi();    for (int i = a.s[n + 1] = 0; i <= n; ++i) b.s[i] = a.s[n - i + 1];    a.get_SA(), a.get_H(), b.get_SA(), b.get_H();    int ans = 1;    for (int len = 1; len <= n; ++len)      for (int i = 1; i + len <= n; i += len) chmax(ans, (a.lcp(i, i + len) + b.lcp(n - i + 1, n - i - len + 1) + len - 1) / len);    cout << ans << endl;  }  return 0;}