c++ - 查找最长公共(public)子串

Question

我需要从两个 DNA 串中找到最长的公共(public)子串。我有第一个字符串“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

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