Envío 7172

Código

import java.util.*;

class Main {
  char T[];
  int n;  

  int[] RA, tempRA;
  Integer[] SA, tempSA;
  int[] c;

  char P[];
  int m;

  int[] Phi;
  int[] PLCP;
  int[] LCP;

  void countingSort(int k) {
    int i, sum, maxi = Math.max(300, n);
    for (i = 0; i < 201000; i++) c[i] = 0;
    for (i = 0; i < n; i++)
      c[i + k < n ? RA[i + k] : 0]++;
    for (i = sum = 0; i < maxi; i++) {
      int t = c[i]; c[i] = sum; sum += t;
    }
    for (i = 0; i < n; i++)
      tempSA[c[SA[i] + k < n ? RA[SA[i] + k] : 0]++] = SA[i];
    for (i = 0; i < n; i++)
      SA[i] = tempSA[i];
  }

  void constructSA() {
    int i, k, r;
    for (i = 0; i < n; i++) RA[i] = T[i];
    for (i = 0; i < n; i++) SA[i] = i;
    for (k = 1; k < n; k <<= 1) {
      countingSort(k);
      countingSort(0);
      tempRA[SA[0]] = r = 0;
      for (i = 1; i < n; i++)
        tempRA[SA[i]] = 
          (RA[SA[i]] == RA[SA[i-1]] && RA[SA[i]+k] == RA[SA[i-1]+k]) ? r : ++r;
      for (i = 0; i < n; i++)
        RA[i] = tempRA[i];
  } }

  void computeLCP() {
    int i, L;
    Phi[SA[0]] = -1;
    for (i = 1; i < n; i++)
      Phi[SA[i]] = SA[i-1];
    for (i = L = 0; i < n; i++) {
      if (Phi[i] == -1) { PLCP[i] = 0; continue; }
      while (i + L < T.length && Phi[i] + L < T.length && T[i + L] == T[Phi[i] + L]) L++;
      PLCP[i] = L;
      L = Math.max(L-1, 0);
    }
    for (i = 1; i < n; i++)
      LCP[i] = PLCP[SA[i]];
  }

  int strncmp(char[] a, int i, char[] b, int j, int n){
    for (int k=0; i+k < a.length && j+k < b.length; k++){
      if (a[i+k] != b[j+k]) return a[i+k] - b[j+k];
    }
    return 0;
  }

  int[] stringMatching() {
    int lo = 0, hi = n-1, mid = lo;
    while (lo < hi) {
      mid = (lo + hi) / 2;
      int res = strncmp(T, SA[mid], P, 0, m);
      if (res >= 0) hi = mid;
      else          lo = mid + 1;
    }
    if (strncmp(T,SA[lo], P,0, m) != 0) return new int[]{-1, -1};
    int[] ans = new int[]{ lo, 0} ;

    lo = 0; hi = n - 1; mid = lo;
    while (lo < hi) {
      mid = (lo + hi) / 2;
      int res = strncmp(T, SA[mid], P,0, m);
      if (res > 0) hi = mid;
      else         lo = mid + 1;
    }
    if (strncmp(T, SA[hi], P,0, m) != 0) hi--;
    ans[1] = hi;
    return ans;
  }

  void LRS() {
    int i, idx = 0, maxLCP = 0;

    for (i = 1; i < n; i++)
      if (LCP[i] > maxLCP) {
        maxLCP = LCP[i];
        idx = i;
      }
  }

  int owner(int idx) { return (idx < n-m-1) ? 1 : 2; }

  int getBorder() {
    int n = T.length;
    int res = -1;
    for(int i = 0; i < n; i += 1) {
      if(SA[i] == 0) {
        res = i;
        break;
      }
    }
    int i = res;
    int mn = LCP[i];
    //System.out.println(i + " " + mn);
    while(i > 0 && (n - 1 - SA[i - 1]) != mn) {
        i -= 1;
        mn = Math.min(mn, LCP[i]);
        //System.out.println(i + " " + mn);
    }
    if(i <= 0 || (n - 1 - SA[i - 1]) != mn) {
        return -1;
    } else {
        return mn;
    }
  }

  void run(String s) {
    int MAX_N = 201000;
    c = new int[MAX_N];
    RA = new int[MAX_N];
    tempRA = new int[MAX_N];
    SA = new Integer[MAX_N];
    tempSA = new Integer[MAX_N];
    Phi = new int[MAX_N];
    PLCP = new int[MAX_N];
    LCP = new int[MAX_N];

    T = s.toCharArray();
    n = T.length;

    constructSA();
    computeLCP();

    int res = getBorder();

    if(res == -1) {
        System.out.println(0);
    } else {
        System.out.println(res);
    }

    /*for(int i = 0; i < n; i += 1) {
        System.out.println(SA[i] + " " + LCP[i]);
    }*/

  }

  public static void main(String[] args){
    
    Scanner scan = new Scanner(System.in);
    new Main().run(scan.nextLine() + "$");
  }
}