La subsecuencia más larga común

Question

He escrito el siguiente código para LCS. Funciona para muchos casos, pero se rompe para el siguiente. No entiendo dónde se está rompiendo mi código. Por favor ayuda. El código está en 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

¿Por qué crees que tu algoritmo está roto? La subsecuencia común más larga es ACCTAGTATTGTTC, que es de 14 caracteres de longitud: (. He modificado su algoritmo para devolver la secuencia en lugar de sólo la longitud)

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

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