Longest Common Successual

Question

Ho scritto il codice seguente per LCS. Funziona in molti casi ma si interrompe per quello qui sotto. Non capisco dove si sta rompendo il mio codice. Per favore aiuto. Il codice è in C#

namespace LongestCommonSubsequenceBF 
{ 
class Program 
{ 
    static void Main(string[] args) 
    { 

     string B = "AAACCGTGAGTTATTCGTTCTAGAA"; 
     string A = "CACCCCTAAGGTACCTTTGGTTC"; 
     //find LCS in A,B starting from index 0 of each 
     int longestCommonSubsequence = LCS(A, B, 0, 0); 
     Console.WriteLine(longestCommonSubsequence); 
     Console.Read(); 

    } 

    //Find the longest common subsequnce starting from index1 in A and index2 in B 
    //Pass A as shorter string 
    public static int LCS(String A, String B, int index1, int index2) 
    { 
     int max = 0; 
     if (index1 == A.Length) 
     { 
      //You have reached beyond A and thus no subsequence 
      return 0; 
     } 
     if (index2 == B.Length) 
     { //you may reach end of 2nd string. LCS from that end is 0 
      return 0; 
     } 

     for (int i = index1; i < A.Length ; i++) 
     { 
      int exist = B.IndexOf(A[i],index2); 
      if (exist != -1) 
      { 
      // found = true; 

       int temp = 1 + LCS(A, B, i + 1, exist + 1); 
       if (max < temp) 
       { 
        max = temp; 
       } 


      } 


     } 
     return max; 

    } 
    } 
} 

Answer 1

Perché pensi che il tuo algoritmo sia rotto? La più lunga sottosequenza comune è ACCTAGTATTGTTC, che è di 14 caratteri: (. Ho modificato l'algoritmo di restituire la sequenza invece di lunghezza)

string B = "AAACCGTGAGTTATTCGTTCTAGAA"; 
       ^^^^^^ ^^^^ ^^^^ 

string A = "CACCCCTAAGGTACCTTTGGTTC"; 
      ^^^^^^ ^^ ^^^^^^