Envío 7169

Problema 0x43 - Encontrar el borde más largo de una string

Autor: Ikerlb
Fecha: 2023-10-05 03:03:24 UTC (Hace alrededor de 1 año)

Caso #	Resultado	Tiempo	Memoria
#1	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.102 s	16 KBi
#2	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.115 s	16 KBi
#3	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.099 s	16 KBi
#4	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.099 s	16 KBi
#5	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.1 s	16 KBi
#6	Correcto	0.107 s	16 KBi
#7	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.201 s	22 KBi
#8	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.237 s	23 KBi
#9	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.188 s	22 KBi
#10	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.22 s	23 KBi
#11	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.208 s	22 KBi
#12	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.232 s	22 KBi
#13	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.228 s	23 KBi
#14	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.231 s	22 KBi
#15	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.237 s	23 KBi
#16	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.238 s	22 KBi
#17	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.203 s	22 KBi
#18	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.23 s	22 KBi
#19	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.214 s	23 KBi
#20	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.188 s	22 KBi
#21	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.24 s	22 KBi
#22	Error en tiempo de ejecución (NZEC) Exited with error status 1 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 100010 out of bounds for length 100010 at Main.countingSort(Main.java:20) at Main.constructSA(Main.java:37) at Main.run(Main.java:138) at Main.main(Main.java:158)	0.227 s	24 KBi

Puntos totales: 5 / 100

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 < 150100; 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;
    while(i > 0 && n - SA[i - 1] != LCP[i]) {
        i -= 1;
    }
    if(i <= 0 || (n - SA[i - 1]) != LCP[i]) {
        return -1;
    } else {
        return LCP[i];
    }
  }

  void run(String s) {
    int MAX_N = 100010;
    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 i = getBorder();

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

    /*for(int i = 0; i < T.length; 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());
  }
}