最长公共子 [英] Longest Common Subsequence

问题描述

我已经写了下面的code为濒海战斗舰。它适用于很多情况下却打破了如下的。我不明白的地方我的code被破坏。请帮忙。在code是在C＃

 命名空间LongestCommonSubsequenceBF
{
类节目
{
    静态无效的主要（字串[] args）
    {

        字符串B =AAACCGTGAGTTATTCGTTCTAGAA;
        字符串A =CACCCCTAAGGTACCTTTGGTTC;
        //找到LCS在A，B各指数0开始
        INT longestCommonSubsequence = LCS（A，B，0，0）;
        Console.WriteLine（longestCommonSubsequence）;
        Console.Read（）;

    }

    //查找最长公共subsequnce从索引1开始在A和索引2 B中
    //传递一个较短的字符串
    公共静态INT LCS（String一个，字符串B，INT指数1，INT索引2）
    {
        INT最大= 0;
        如果（索引1 ==则为a.length）
        {
            //您已达到超越，因此没有子
            返回0;
        }
        如果（索引2 == b.length个）
        {//你可能会达到第二个字符串的结尾。 LCS从该端为0
            返回0;
        }

        的for（int i =索引1; I＆LT;则为a.length;我++）
        {
            INT存在= B.IndexOf（A [1]，索引2）;
            如果（存在！= -1）
            {
             //发现= TRUE;

                INT TEMP = 1 + LCS（A，B，I + 1，存在+ 1）;
                如果（MAX＆LT;温度）
                {
                    MAX =温度;
                }


            }


        }
        返回最大值;

    }
  }
}
 

解决方案

为什么你认为你的算法被破解？最长的公共子是 ACCTAGTATTGTTC ，这是14个字符：

 字符串B =AAACCGTGAGTTATTCGTTCTAGAA;
              ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

字符串A =CACCCCTAAGGTACCTTTGGTTC;
             ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
 

（我修改了算法，仅返回长的序列代替。）

I have written the below code for LCS. It works for many cases but breaks for the one below. I do not understand where my code is breaking. Please help. The code is 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;

    }
  }
}

解决方案

Why do you think your algorithm is broken? The longest common subsequence is ACCTAGTATTGTTC, which is 14 characters long:

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

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

(I modified your algorithm to return the sequence instead of just the length.)

这篇关于最长公共子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！