fork download
copy 
  1. // Problema: Longest Repeating Substring
  2. // Descripcion: Encontrar en una cadena de texto la subcadena de texto mas larga que se repite mas de 1 vez
  3. // Juez Virtual: https://c...content-available-to-author-only...s.fi/problemset/task/2106
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. // Construcción del Suffix Array usando el algoritmo de doubling O(n log² n)
  9. // (versión con sort en lugar de counting sort)
  10. vector<int> construct_suffix_array(string s) {
  11.     s += "$"; // Agregamos un carácter centinela menor que cualquier otro
  12.     int n = s.length();
  13.     vector<int> suffix_array(n);
  14.  
  15.     // Inicialmente, los sufijos se ordenan por su primer carácter
  16.     for (int i = 0; i < n; i++) {
  17.         suffix_array[i] = n - i - 1;
  18.     }
  19.  
  20.     // Orden estable por el primer carácter
  21.     stable_sort(suffix_array.begin(), suffix_array.end(), [&] (int i, int j) {
  22.         return s[i] < s[j]; 
  23.     });
  24.  
  25.     // Asignamos clases (rank) según el carácter inicial
  26.     vector<int> rank(n);
  27.     rank[suffix_array[0]] = 0;
  28.     for (int i = 1; i < n; i++) {
  29.         if (s[suffix_array[i]] != s[suffix_array[i - 1]]) {
  30.             rank[suffix_array[i]] = rank[suffix_array[i - 1]] + 1;
  31.         }
  32.         else {
  33.             rank[suffix_array[i]] = rank[suffix_array[i - 1]];
  34.         }
  35.     }
  36.  
  37.     // Doblamos la longitud del prefijo comparado en cada iteración
  38.     for (int k = 0; (1 << k) < n; k++) {
  39.         vector<pair<int, int>> pairs(n);
  40.  
  41.         // Cada sufijo se representa por un par (rank actual, rank desplazado)
  42.         for (int i = n - 1; i >= 0; i--) {
  43.             pairs[i] = {rank[i], rank[(i + (1 << k)) % n]};
  44.         }
  45.  
  46.         // Ordenamos según los pares (clave doble)
  47.         sort(suffix_array.begin(), suffix_array.end(), [&] (int i, int j) {
  48.             return pairs[i] < pairs[j];
  49.         });
  50.  
  51.         // Reasignamos los nuevos ranks según el orden obtenido
  52.         rank[suffix_array[0]] = 0;
  53.         for (int i = 1; i < n; i++) {
  54.             if (pairs[suffix_array[i]] != pairs[suffix_array[i - 1]]) {
  55.                 rank[suffix_array[i]] = rank[suffix_array[i - 1]] + 1;
  56.             }
  57.             else {
  58.                 rank[suffix_array[i]] = rank[suffix_array[i - 1]];
  59.             }
  60.         }
  61.     }
  62.  
  63.     // Quitamos la posición del sufijo que empieza con '$'
  64.     suffix_array.erase(suffix_array.begin());
  65.     return suffix_array;
  66. }
  67.  
  68. // Construcción del arreglo LCP (Longest Common Prefix) en O(n)
  69. // LCP[i] = longitud del prefijo común entre sufijos SA[i] y SA[i+1]
  70. vector<int> construct_lcp(string& s, vector<int>& suffix_array) {
  71.     int n = s.length();
  72.     vector<int> lcp(n - 1);
  73.     vector<int> rank(n);
  74.  
  75.     // rank[i] = posición del sufijo que empieza en i dentro del SA
  76.     for (int i = 0; i < n; i++) {
  77.         rank[suffix_array[i]] = i;
  78.     }
  79.  
  80.     int k = 0; // longitud actual del prefijo común
  81.  
  82.     for (int i = 0; i < n; i++) {
  83.         if (rank[i] == n - 1) {
  84.             continue; // último sufijo, no tiene siguiente
  85.         }
  86.  
  87.         int j = suffix_array[rank[i] + 1]; // siguiente sufijo en el SA
  88.  
  89.         // Calculamos LCP comparando carácter por carácter
  90.         while (i + k < n && j + k < n && s[i + k] == s[j + k]) k++;
  91.  
  92.         lcp[rank[i]] = k; // guardamos el resultado
  93.  
  94.         if (k > 0) k--; // optimización: siguiente comparación empieza con k-1
  95.     }
  96.  
  97.     return lcp;
  98. }
  99.  
  100. int main() {
  101.     cin.tie(0);
  102.     ios_base::sync_with_stdio(0);
  103.  
  104.     string s;
  105.     cin >> s;
  106.     int n = s.length();
  107.  
  108.     // Caso trivial: solo un carácter, no hay repeticiones
  109.     if (n == 1) {
  110.         cout << -1 << endl;
  111.         exit(0);
  112.     }
  113.  
  114.     // Construimos el SA y el arreglo LCP
  115.     vector<int> suffix_array = construct_suffix_array(s);
  116.     vector<int> lcp = construct_lcp(s, suffix_array);
  117.  
  118.     // Buscamos el valor máximo del LCP (la subcadena repetida más larga)
  119.     int mx = *max_element(lcp.begin(), lcp.end());
  120.     int ind = 0;
  121.     while (lcp[ind] != mx) ind++;
  122.  
  123.     // Si no hay repeticiones, imprimimos -1
  124.     if (mx == 0) {
  125.         cout << -1 << endl;
  126.         exit(0);
  127.     }
  128.  
  129.     // Imprimimos la subcadena repetida más larga
  130.     for (int i = 0; i < mx; i++) {
  131.         cout << s[suffix_array[ind] + i];
  132.     }
  133.  
  134.     cout << endl;
  135. }
  136.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
cabababc
stdout
copy 
abab
https://ideone.com/47t3AH
language:
C++ (gcc 8.3)
created:
13 days ago
visibility:
public

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!