Cómo encontrar la subcadena común más larga usando C++

Question

Busqué en línea una implementación de subcadena común más larga en C++ pero no pude encontrar una decente. Necesito un algoritmo LCS que devuelva la subcadena en sí, así que no es solo LCS.

Me preguntaba, sin embargo, acerca de cómo puedo hacer esto entre múltiples cadenas.

Mi idea era comprobar la más larga entre 2 cadenas, y luego comprobar todas las demás, pero este es un proceso muy lento que requiere gestionar muchas cadenas largas en la memoria, haciendo que mi programa sea bastante lento.

¿Alguna idea de cómo se puede acelerar esto para múltiples cadenas? Gracias.

Editar Importante Una de las variables que estoy dado determina el número de cadenas de la subcadena común más larga tiene que estar en, por lo que se puede dar 10 cuerdas, y encontrar la LCS de todos ellos (K = 10), o LCS de 4 de ellos, pero no me dicen cuál 4, tengo que encontrar el mejor 4.

Answer 1

Aquí hay un excelente artículo sobre finding all common substrings de manera eficiente, con ejemplos en C. Esto puede ser exagerado si necesita el más largo, pero puede ser más fácil de entender que los artículos generales sobre árboles de sufijos.

Answer 2

Encuentra la subcadena más grande de todas las cadenas en consideración. Desde N strings, tendrás N subcadenas. Elija el más grande de ésos N.

Answer 3

La respuesta es GENERALIZED SUFFIX TREE. http://en.wikipedia.org/wiki/Generalised_suffix_tree

Puede construir un árbol de sufijo generalizado con varias cadenas.

mirada a este árbol http://en.wikipedia.org/wiki/Longest_common_substring_problem

el sufijo puede ser construido en tiempo O (n) para cada cadena, k * O (n) en total. K es el número total de cadenas.

Así que es muy rápido para resolver este problema.

Answer 4

Este es un problema de programación dinámica y se puede resolver en el tiempo O (mn), donde m es la longitud de una cadena yn es de otra.

Al igual que cualquier otro problema resuelto mediante la programación dinámica, dividiremos el problema en subproblemas. Digamos que si dos cadenas son X1X2X3 .... XM y y1y2y3 ... yn

S (i, j) es la cadena más larga común para X1X2X3 ... XI y y1y2y3 .... yj, a continuación,

S (i, j) = max { longitud de la subcadena común más larga que termina en xi/yj, if (x [i] == y [j]), S (i-1, j-1), S (i, j-1), S (i-1, j) }

Aquí está el programa de trabajo en Java. Estoy seguro de que puedes convertirlo a C++.:

public class LongestCommonSubstring { 

    public static void main(String[] args) { 
     String str1 = "abcdefgijkl"; 
     String str2 = "mnopabgijkw"; 
     System.out.println(getLongestCommonSubstring(str1,str2)); 
    } 

    public static String getLongestCommonSubstring(String str1, String str2) { 
     //Note this longest[][] is a standard auxialry memory space used in Dynamic 
       //programming approach to save results of subproblems. 
       //These results are then used to calculate the results for bigger problems 
     int[][] longest = new int[str2.length() + 1][str1.length() + 1]; 
     int min_index = 0, max_index = 0; 

       //When one string is of zero length, then longest common substring length is 0 
     for(int idx = 0; idx < str1.length() + 1; idx++) { 
      longest[0][idx] = 0; 
     } 

     for(int idx = 0; idx < str2.length() + 1; idx++) { 
      longest[idx][0] = 0; 
     } 

     for(int i = 0; i < str2.length(); i++) { 
      for(int j = 0; j < str1.length(); j++) { 

       int tmp_min = j, tmp_max = j, tmp_offset = 0; 

       if(str2.charAt(i) == str1.charAt(j)) { 
        //Find length of longest common substring ending at i/j 
        while(tmp_offset <= i && tmp_offset <= j && 
          str2.charAt(i - tmp_offset) == str1.charAt(j - tmp_offset)) { 

         tmp_min--; 
         tmp_offset++; 

        } 
       } 
       //tmp_min will at this moment contain either < i,j value or the index that does not match 
       //So increment it to the index that matches. 
       tmp_min++; 

       //Length of longest common substring ending at i/j 
       int length = tmp_max - tmp_min + 1; 
       //Find the longest between S(i-1,j), S(i-1,j-1), S(i, j-1) 
       int tmp_max_length = Math.max(longest[i][j], Math.max(longest[i+1][j], longest[i][j+1])); 

       if(length > tmp_max_length) { 
        min_index = tmp_min; 
        max_index = tmp_max; 
        longest[i+1][j+1] = length; 
       } else { 
        longest[i+1][j+1] = tmp_max_length; 
       } 


      } 
     } 

     return str1.substring(min_index, max_index >= str1.length() - 1 ? str1.length() - 1 : max_index + 1); 
    } 
} 

Answer 5

Aquí está una versión de C# para encontrar el común más larga subcadena utilizando programación dinámica de dos matrices (que puede referirse a: http://codingworkout.blogspot.com/2014/07/longest-common-substring.html para más detalles)

class LCSubstring 
     { 
      public int Length = 0; 
      public List<Tuple<int, int>> indices = new List<Tuple<int, int>>(); 
     } 
     public string[] LongestCommonSubStrings(string A, string B) 
     { 
      int[][] DP_LCSuffix_Cache = new int[A.Length+1][]; 
      for (int i = 0; i <= A.Length; i++) 
      { 
       DP_LCSuffix_Cache[i] = new int[B.Length + 1]; 
      } 
      LCSubstring lcsSubstring = new LCSubstring(); 
      for (int i = 1; i <= A.Length; i++) 
      { 
       for (int j = 1; j <= B.Length; j++) 
       { 
        //LCSuffix(Xi, Yj) = 0 if X[i] != X[j] 
        //     = LCSuffix(Xi-1, Yj-1) + 1 if Xi = Yj 
        if (A[i - 1] == B[j - 1]) 
        { 
         int lcSuffix = 1 + DP_LCSuffix_Cache[i - 1][j - 1]; 
         DP_LCSuffix_Cache[i][j] = lcSuffix; 
         if (lcSuffix > lcsSubstring.Length) 
         { 
          lcsSubstring.Length = lcSuffix; 
          lcsSubstring.indices.Clear(); 
          var t = new Tuple<int, int>(i, j); 
          lcsSubstring.indices.Add(t); 
         } 
         else if(lcSuffix == lcsSubstring.Length) 
         { 
          //may be more than one longest common substring 
          lcsSubstring.indices.Add(new Tuple<int, int>(i, j)); 
         } 
        } 
        else 
        { 
         DP_LCSuffix_Cache[i][j] = 0; 
        } 
       } 
      } 
      if(lcsSubstring.Length > 0) 
      { 
       List<string> substrings = new List<string>(); 
       foreach(Tuple<int, int> indices in lcsSubstring.indices) 
       { 
        string s = string.Empty; 
        int i = indices.Item1 - lcsSubstring.Length; 
        int j = indices.Item2 - lcsSubstring.Length; 
        Assert.IsTrue(DP_LCSuffix_Cache[i][j] == 0); 
        for(int l =0; l<lcsSubstring.Length;l++) 
        { 
         s += A[i]; 
         Assert.IsTrue(A[i] == B[j]); 
         i++; 
         j++; 
        } 
        Assert.IsTrue(i == indices.Item1); 
        Assert.IsTrue(j == indices.Item2); 
        Assert.IsTrue(DP_LCSuffix_Cache[i][j] == lcsSubstring.Length); 
        substrings.Add(s); 
       } 
       return substrings.ToArray(); 
      } 
      return new string[0]; 
     } 

Cuando las pruebas de unidad son:

[TestMethod] 
     public void LCSubstringTests() 
     { 
      string A = "ABABC", B = "BABCA"; 
      string[] substrings = this.LongestCommonSubStrings(A, B); 
      Assert.IsTrue(substrings.Length == 1); 
      Assert.IsTrue(substrings[0] == "BABC"); 
      A = "ABCXYZ"; B = "XYZABC"; 
      substrings = this.LongestCommonSubStrings(A, B); 
      Assert.IsTrue(substrings.Length == 2); 
      Assert.IsTrue(substrings.Any(s => s == "ABC")); 
      Assert.IsTrue(substrings.Any(s => s == "XYZ")); 
      A = "ABC"; B = "UVWXYZ"; 
      string substring = ""; 
      for(int i =1;i<=10;i++) 
      { 
       A += i; 
       B += i; 
       substring += i; 
       substrings = this.LongestCommonSubStrings(A, B); 
       Assert.IsTrue(substrings.Length == 1); 
       Assert.IsTrue(substrings[0] == substring); 
      } 
     } 

Answer 6

Hay una solución de programación dinámica muy elegante para esto.

Deje LCSuff[i][j] ser el sufijo común más largo entre X[1..m] y Y[1..n]. Tenemos dos casos aquí:

• X[i] == Y[j], que significa que podemos ampliar el sufijo común más larga entre X[i-1] y Y[j-1]. Por lo tanto, LCSuff[i][j] = LCSuff[i-1][j-1] + 1 en este caso.

• X[i] != Y[j], ya que los últimos personajes mismos son diferentes, X[1..i] y Y[1..j] no se puede tener un sufijo común. Por lo tanto, LCSuff[i][j] = 0 en este caso.

Ahora tenemos que comprobar el máximo de estos sufijos comunes más largos.

Así, LCSubstr(X,Y) = max(LCSuff(i,j)), donde 1<=i<=m y 1<=j<=n

El algoritmo escribe más o menos en sí mismo.

string LCSubstr(string x, string y){ 
    int m = x.length(), n=y.length(); 

    int LCSuff[m][n]; 

    for(int j=0; j<=n; j++) 
     LCSuff[0][j] = 0; 
    for(int i=0; i<=m; i++) 
     LCSuff[i][0] = 0; 

    for(int i=1; i<=m; i++){ 
     for(int j=1; j<=n; j++){ 
      if(x[i-1] == y[j-1]) 
       LCSuff[i][j] = LCSuff[i-1][j-1] + 1; 
      else 
       LCSuff[i][j] = 0; 
     } 
    } 

    string longest = ""; 
    for(int i=1; i<=m; i++){ 
     for(int j=1; j<=n; j++){ 
      if(LCSuff[i][j] > longest.length()) 
       longest = x.substr((i-LCSuff[i][j]+1) -1, LCSuff[i][j]); 
     } 
    } 
    return longest; 
}