Hậu quả chung dài nhất

Question

Tôi đã viết mã dưới đây cho LCS. Nó hoạt động trong nhiều trường hợp nhưng phá vỡ cho một trong những bên dưới. Tôi không hiểu mã của tôi đang ở đâu. Hãy giúp tôi. Mã này nằm trong 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

Tại sao bạn nghĩ thuật toán của mình bị hỏng? Các dãy con chung dài nhất là ACCTAGTATTGTTC, đó là 14 ký tự dài: (. Tôi đã sửa đổi thuật toán của bạn để trả lại chuỗi thay vì chỉ độ dài)

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

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