查找最长的公共子字符串

Question

我需要从两个DNA字符串中找到最长的公共子字符串。我有第一个字符串“ CGATAC”，第二个是“ GACAGTC”用我的代码，我的结果是：“ GAC”，但是您可以获得更长的子字符串，我的意思是“ GATC”。我需要更改以获得更长的子字符串吗？

int k = 0;
for (int i = 0; i < substring1.length(); i++) {
    char znak = substring1[i];
    for (int j = k; j < substring2.length(); j++) {
        char znak2 = substring2[j];
        if (znak == znak2) {
            end_substring += znak;
            k = j;
            break;
        }
    }
}
cout << end_substring;

Answer 1

您可以通过一些基本思路来改进代码。我知道您想要最长的字符串而不是全部的[[one，那么您可以存储最长的字符串的长度，直到程序中的每个时刻为止，并将此长度用于搜索字符串，长度至少为length + 1。但是bes解决方案是使用动态porgramming，您可以在此处阅读此解决方案：https://www.geeksforgeeks.org/longest-common-substring-dp-29/

Answer 2

如果需要在substring2中找到substring1，那么可能有必要创建一个三重循环或一个函数以正确的顺序在substring1中找到整个substring2。

这是我的位置：

string solve(string str1, string str2, int n) 
{
    string reStr = "";
    int j = 0;
    for (int i = n; i < str1.length(); i++)
    {
        if(str1[i]==str2[j])
        {
            reStr += str1[i++];
            j++;
            while (str1[i++] == str2[j++])
            {
                reStr += str1[i-1];
            }
        }
    }
    return reStr;
}

int main()
{
    string substring1 = "ABCDABCD";
    string substring2 = "DABC";

    string reValue = "";
    for (int i = 0; i < substring1.length(); i++)
    {
        string tempStr = solve(substring1, substring2, i);
        if (reValue.length() <= tempStr.length())
        {
            reValue = tempStr;
        }
    }
    cout<<reValue;
}