最长公共子序列

Question

嗨，这是我在c#中为2个字符串编写的最长公共子序列的代码。我需要回溯方面的帮助。我需要找出子序列: GTCGT

String str1 = "GTCGTTCG";
String str2 = "ACCGGTCGAGTG";

int[,] l = new int[str1.Length, str2.Length]; // String 1 length and string 2      length storing it in a 2-dimensional array
int lcs = -1;
string substr = string.Empty;
int end = -1;

for (int i = 0; i <str1.Length ; i++) // Looping based on string1 length 
{                
  for (int j = 0; j < str2.Length; j++) // Looping based on string2 Length
  {                  
    if (str1[i] == str2[j]) // if match found 
    {
      if (i == 0 || j == 0)  // i is first element or j is first elemnt then array [i,j] = 1
      {
        l[i, j] = 1;
      }
      else
      {   
        l[i, j] = l[i - 1, j - 1] + 1; // fetch the upper value and increment by 1 
      }

      if (l[i, j] > lcs)
      {
        lcs = l[i, j]; // store lcs value - how many time lcs is found 
        end = i; // index on longest continuous string
      }

    }
    else // if match not found store zero initialze the array value by zero
    {
      l[i, j] = 0;
    }
}

Answer 1

您的函数需要返回一个字符串集合。可能存在几个长度相同的最长的公共子序列。

public List<string> LCS(string firstString, string secondString)
{
    // to create the lcs table easier which has first row and column empty.
    string firstStringTemp = " " + firstString;
    string secondStringTemp = " " + secondString;

    // create the table
    List<string>[,] temp = new List<string>[firstStringTemp.Length, secondStringTemp.Length];

    // loop over all items in the table.
    for (int i = 0; i < firstStringTemp.Length; i++)
    {
        for (int j = 0; j < secondStringTemp.Length; j++)
        {

            temp[i, j] = new List<string>();
            if (i == 0 || j == 0) continue;
            if (firstStringTemp[i] == secondStringTemp[j])
            {
                var a = firstStringTemp[i].ToString();
                if (temp[i - 1, j - 1].Count == 0)
                {
                    temp[i, j].Add(a);
                }
                else
                {
                    foreach (string s in temp[i - 1, j - 1])
                    {
                        temp[i, j].Add(s + a);
                    }
                }
            }
            else
            {
                List<string> b = temp[i - 1, j].Concat(temp[i, j - 1]).Distinct().ToList();
                if (b.Count == 0) continue;
                int max = b.Max(p => p.Length);
                b = b.Where(p => p.Length == max).ToList();
                temp[i, j] = b;
            }
        }
    }
    return temp[firstStringTemp.Length - 1, secondStringTemp.Length - 1];
}

您需要在表的每个条目中有一个收集组。因此，您仍然可以在表的每个单元格中保留相同长度的不同字符串。

Answer 2

就我对你的问题的理解而言，我认为你想知道后续值，即那个字符串。因此，为了获得后续序列，我学到了一些不同的东西。首先，我计算了我们在标准最长公共子序列(LCS)问题中使用的表。然后，我遍历表以获得子序列值。对不起，我不熟悉C#，所以我会给你CPP代码。如果你遇到任何问题，请看一看，让我知道。

#include<iostream>
#include<vector>
#include<string>
using namespace std;


string printLongestCommonSubsequence(vector<vector<int> >& dp, int m, int n, string text1, string text2){
    int i = m, j = n;
    string lcs = "";
    while(i > 0 && j > 0){
        if(text1[i-1] == text2[j-1]){
            lcs.push_back(text1[i-1]);
            i--; j--;
        }
        else{
            if(dp[i][j-1] > dp[i-1][j]) j--;
            else i--;
        }
    }
    reverse(lcs.begin(), lcs.end());
    return lcs;
}

string longestCommonSubsequence(string text1, string text2){
    int m = text1.size();
    int n = text2.size();
    vector<vector<int> > dp(m+1, vector<int>(n+1));

    //initialization
    for(int i=0; i<m+1; i++){
        for(int j=0; j<n+1; j++){
            if(i == 0 || j == 0) dp[i][j] = 0;
        }
    }

    //solving the subproblems to solve the bigger problems
    for(int i=1; i<m+1; i++){
        for(int j=1; j<n+1; j++){
            if(text1[i-1] == text2[j-1])
                dp[i][j] = 1 + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }

    return printLongestCommonSubsequence(dp, m, n, text1, text2);
}

int main(){
    string text1, text2;
    cout<<"Enter the first string: ";
    cin>>text1;
    cout<<"\nEnter the second string: ";
    cin>>text2;

    string lcs = longestCommonSubsequence(text1, text2);
    cout<<"Longest Common Subsequence is: "<<lcs<<endl;
    return(0);
}

​

​

请看一下图表。关于打印LCS，基本思想是：

1. 当两个字符串的字符相等时，则朝对角线方向移动。
2. 当字符不等于两个字符串时，则朝两个方向中的最大值移动。

我希望这对快乐学习有帮助谢谢