Längste gemeinsame Subsequenz

Question

Ich habe den folgenden Code für LCS geschrieben. Es funktioniert für viele Fälle, aber bricht für den folgenden. Ich verstehe nicht, wo mein Code bricht. Bitte helfen Sie. Der Code ist 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

Warum denken Sie, dass Ihr Algorithmus defekt ist? Die längste gemeinsame Teilfolge ist ACCTAGTATTGTTC, die 14 Zeichen lang ist: (i. Ihr Algorithmus modifiziert, um die Sequenz, anstatt nur die Länge zurückzukehren)

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

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