最も長い共通部分列

Question

私はLCSのために以下のコードを書いています。これは多くの場合に機能しますが、下のものでは機能しません。私のコードがどこで壊れているのか分かりません。助けてください。コードは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

なぜあなたのアルゴリズムは壊れていると思いますか？最長共通部分列は、14文字の長され、ACCTAGTATTGTTC次のとおりです。

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

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

（私はシーケンスの代わりに長さだけを返すようにアルゴリズムを変更しました。）