Resolviendo el #TuentiContest: Problema 8 – The Biologist Problem

Hola gente. Aprovecharé esta entrada para felicitar públicamente a los ganadores del concurso. ¡Enhorabuena! Mucha gente logró completar todos los desafíos, lo que demuestra que no sólo saben programar sino que tienen la curiosidad y la terquedad (en buen sentido) suficiente para enfrentarse a problemas con poca información. Mientras tanto, yo sigo publicando mis soluciones con la intención de enseñar un poquito el tipo de retos típico de estos eventos y más importante aún, cómo llegar a su solución. La idea es animar a estudiantes de carrera a participar y mantener con todos una conversación que nos afine nuestras habilidades en algorítmicas. El problema 8, sigue la línea del problema anterior, pidiéndonos información sobre cadenas de caracteres. Ahora, dada dos cadenas que representan secuencias de ADN, nos piden calcular cuál es la subcadena común más larga de ambas. Siguiendo con mi tiqui-taca entre C++ y Java, ahora toca una solución en C++. Este problema es el hermano menor de un problema más general, en el que se calcula la secuencia común más larga entre dos cadenas de caracteres. Análisis del problema Con un poco menos de dedicación pero igualmente claro, nos explican que lo que desean es la subcadena común más larga entre dos cadenas de caracteres. Tomando el ejemplo del planteamiento: dada las cadenas ATGTCTTCCTCGA y  TGCTTCCTATGAC, nos piden encontrar la subcadena CTTCCT, pues es la subcadena común más larga para este par. Comencemos entonces. De entrada tenemos la opción obvia que es probar todas las subcadenas posibles de una de ellas e ir revisando si aparece en la otra. Sin embargo, un poco de análisis a este algoritmo nos muestra un orden O(n⁴) aproximadamente (cuadrático para extraer una subcadena y cuadrático de nuevo para revisarla en la otra). Así que mejor buscamos otra manera. Hasta ahora entre las herramientas que hemos usado para los problemas anteriores, una de las más recurrentes (será casualidad la redundancia) ha sido la recursión. Así que, al igual que en el problema anterior, imaginemos que estamos a mitad de camino en nuestro cálculo (ya hemos revisado i-1 y j-1 caracteres en ambas cadenas) y estamos comparando las posiciones i y j. Nuevamente pueden ocurrir dos cosas, o los caracteres son iguales, o no lo son. Pero en este caso la decisión a tomar es mucho más sencilla pues si no son iguales, no nos interesa seguir; si coinciden, nuestra cadena más larga aumenta en 1 su tamaño. Por lo tanto, utilizando la notación del problema 7, nuestra recursión sería: length(i,j) = (a(i)==b(j)) ? length(i-1,j-1)+1 : 0 Mucho mejor, ahora nuestro orden es O(n²). Pero aún no hemos terminado. A diferencia del problema de las fichas, no nos piden la longitud de la subcadena, sino cuál es. Será necesario entonces agregar algunos indicadores a nuestra recursión para que recuerden dónde está ubicada la solución. En este caso, como lo que nos piden es una subcadena, necesitamos saber al menos cuál es su longitud y dónde acaba. Y la misma recursión nos ofrece esa información. Solo debemos recordar el máximo valor de length(i,j) y la posición i (o la j) en la que ocurrió. Ahora sí,  a implementar la solución con bottom-up. Solución enviada La solución en C++ es bastante sencilla. El método lcs calculará la máxima subcadena, devolviendo su longitud y la posición de su último caracter en la primera cadena. Incluye además una pequeña verificación en la línea 15 para no caer en índices negativos. Las líneas [20,…,23] son las que recuerdan la máxima longitud y su ubicación. Finalmente, la línea 38 es la que extrae la subcadena encontrada.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

pair  <int,int> lcs(const string& s1, const string& s2){
  int max = 0;
  int last = 0;
  vector  <vector  <int> > memo(s1.length(),vector<int>(s2.length(),0));

  for(size_t i=0;i  <s1.length();i++){
    for(size_t j=0;j  <s2.length();j++){
      if(s1.c_str()[i] == s2.c_str()[j]){
        if(i==0 || j==0){
          memo[i][j] = 1;
        } else {
          memo[i][j] = memo[i-1][j-1]+1;
        }
        if(max   < memo[i][j]) {
          max = memo[i][j];
          last = i;
        }
      }
    }
  }

  return pair  <int,int>(last,max);
}

int main() {
  string line;
  while(getline(cin, line)){
    size_t space = line.find(' ');
    string s1 = line.substr(0,space);
    string s2 = line.substr(space+1);
    pair  <int,int> p = lcs(s1,s2);
    string common = s1.substr(p.first-p.second+1,p.second);
    cout   <  < common   <  < endl;
  }
}

Solución mejorada Existe una solución más eficiente aún, de orden O(n+m) que hace uso de una estructura de datos denominada Árboles de Sufijo Genéricos (que en inglés suena más bonito, Generalised Suffix Tree), que es una especie de Trie “al revés”. Pueden verla con más detalle en Wikipedia. Yo conocía de antemano la solución con programación dinámica que les he mostrado y por eso fui directamente a esta implementación. Sin embargo, soluciones más eficientes siempre son bienvenidas. Si alguien la implementó, me gustaría verla. Con la mención de los Suffix Trees (aunque ya fuera de la solución del problema) aprovecho para comentarles de otra estructura similar (pues maneja sufijos): los Suffix Arrays. Estos últimos guardan los sufijos en arreglos en vez de árboles (eso se veía venir) y han sido utilizados para diversos fines en el área de la traducción automática. Solo eso, una anécdota. He visto entre las soluciones publicadas de los otros participantes programas que consideran todos los casos uno por uno. Dependiendo de la rudeza de las pruebas, es posible que dichos programas tarden mucho más de lo necesario para hallar la solución. En fin, ¿cómo lo resolviste?