2

嗨，这是我的 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;
    }
}
4

2 回答 2

0

据我了解您的问题，我认为您想知道子序列值，即该字符串。所以，为了得到子序列，我学到了一些不同的东西。首先，我计算我们在标准最长公共子序列（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. 当两个字符串的字符不相等时，则向两个方向的最大值移动。

我希望这有助于快乐学习谢谢

于 2021-11-04T06:46:56.690 回答
0

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

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];
}

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

于 2018-09-08T00:05:47.057 回答