█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 7164

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

  • Autor: Ikerlb
  • Fecha: 2023-10-05 02:31:38 UTC (Hace alrededor de 1 año)
Caso # Resultado Tiempo Memoria
#1
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#2
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#3
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#4
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#5
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#6
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#7
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#8
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#9
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#10
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#11
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#12
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#13
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#14
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#15
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#16
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#17
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#18
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#19
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#20
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#21
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
#22
Error de compilación 
                      Main.java:157: error: cannot find symbol
    new sa_lcp().run(scan.nextLine());
        ^
  symbol:   class sa_lcp
  location: class Main
1 error
Puntos totales: 0 / 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 < 100010; 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(n - SA[i - 1] == LCP[i]) {
        return LCP[i];
    }
    return -1;
  }

  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 sa_lcp().run(scan.nextLine());
  }
}