Come trovare la sottostringa comune più lunga usando C++

Question

Ho cercato online un'implementazione di sottostringa comune più lunga del C++ ma non sono riuscito a trovarne uno decente. Ho bisogno di un algoritmo LCS che restituisca la sottostringa stessa, quindi non è solo LCS.

Mi chiedevo, tuttavia, su come posso farlo tra più stringhe.

La mia idea era quella di controllare il più lungo tra 2 stringhe, e quindi andare a controllare tutti gli altri, ma questo è un processo molto lento che richiede la gestione di molte stringhe lunghe sulla memoria, rendendo il mio programma piuttosto lento.

Qualche idea di come questo può essere accelerato per più stringhe? Grazie.

Modifica Importante Una delle variabili che sono dato determina il numero di stringhe più lunghe sottostringa comune deve essere in, così ho può essere dato 10 corde, e trovare le LCS di tutti loro (K = 10), o LCS di 4 di loro, ma non mi viene detto quale 4, devo trovare il migliore 4.

Answer 1

Ecco un eccellente articolo su finding all common substrings in modo efficiente, con esempi in C. Questo può essere eccessivo se è necessario solo il più lungo, ma può essere più facile da capire rispetto agli articoli generali sugli alberi dei suffissi.

Answer 2

Trova la sottostringa più grande tra tutte le stringhe considerate. Da stringhe N, avrai sottostringhe N. Scegli il più grande di quelli N.

Answer 3

La risposta è ALBERO SUFFICE GENERALIZZATO. http://en.wikipedia.org/wiki/Generalised_suffix_tree

È possibile creare un albero di suffisso generalizzato con più stringhe.

Guardate questo albero http://en.wikipedia.org/wiki/Longest_common_substring_problem

il suffisso può essere costruito in O (n) per ogni corda, k * O (n) in totale. K è il numero totale di stringhe.

Quindi è molto veloce per risolvere questo problema.

Answer 4

Questo è un problema di programmazione dinamica e può essere risolto nel tempo O (mn), dove m è la lunghezza di una stringa en è dell'altro.

Come qualsiasi altro problema risolto utilizzando la Programmazione dinamica, suddivideremo il problema in sottoproblema. Consente di dire se due stringhe sono X1X2X3 .... xm e y1y2y3 ... yn

S (i, j) è la stringa più lunga comuni per X1X2X3 ... xi e y1y2y3 .... YJ, poi

S (i, j) = max { lunghezza della sottostringa comune più lunga che termina con xi/yj, if (x [i] == y [j]), S (i-1, j-1), S (i, j-1), S (i-1, j) }

Qui è un programma funzionante in Java. Sono sicuro che puoi convertirlo in 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

Ecco una versione C# per trovare la più lunga Comune Substring usando la programmazione dinamica di due array (si può riferirsi a: http://codingworkout.blogspot.com/2014/07/longest-common-substring.html per maggiori dettagli)

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]; 
     } 

Dove unit test sono:

[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

C'è una soluzione di programmazione dinamica molto elegante a questo.

Lascia che LCSuff[i][j] sia il suffisso più lungo tra X[1..m] e Y[1..n]. Abbiamo due casi qui:

• X[i] == Y[j], che significa che possiamo estendere il suffisso comune più lungo fra X[i-1] e Y[j-1]. Quindi LCSuff[i][j] = LCSuff[i-1][j-1] + 1 in questo caso.

• X[i] != Y[j], poiché gli ultimi caratteri sono diversi, X[1..i] e Y[1..j] non possono avere un suffisso comune. Quindi, LCSuff[i][j] = 0 in questo caso.

Ora è necessario controllare il massimo di questi suffissi comuni più lunghi.

Quindi, LCSubstr(X,Y) = max(LCSuff(i,j)), dove 1<=i<=m e 1<=j<=n

L'algoritmo si scrive più o meno ora.

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; 
}