1

这两个字符串 {xaybadfeg, abcdefg} 的最长公共子序列是什么。不是“abdeg”吗？我正在使用这个算法（动态编程技术）来寻找解决方案。它返回“adeg”作为答案。我对子序列的理解是错误的吗？我的算法错了吗？我错过了什么吗？我应该为这种类型的输入提供特殊情况吗？

动态编程代码

#include <iostream>
#include <stack>
using namespace std;

void LCS(string str1, string str2){
    int out[100][100] = {};
    for (int i = 0; i <= str1.size(); i++){
        for (int j = 0; j <= str2.size(); j++){
            if (i == 0 || j == 0)
                out[i][j] = 0;
            else{
                if (str1[i-1] == str2[j-1]){
                    if (out[i][j - 1] > out[i - 1][j])
                        out[i][j] = out[i][j - 1] + 1;
                    else
                        out[i][j] = out[i - 1][j] + 1;
                }
                else{
                    if (out[i][j - 1] > out[i - 1][j])
                        out[i][j] = out[i][j - 1];
                    else
                        out[i][j] = out[i - 1][j];
                }
            }
        }
    }

    //Backtracing to print the numbers
    int i = str1.size()-1, j = str2.size()-1;
    std::string subSeqStr="";
    while (i >= 0 || j >= 0){
        if (str2[j] != str1[i]){
            if (out[i][j - 1] > out[i - 1][j])
                j--;
            else
                i--;
        }
        else{
            subSeqStr.insert(subSeqStr.begin(), str2[j]);
            i--; j--;
        }
    }
    std::cout << "The least common subsequence is: " << subSeqStr<< std::endl;
}

int main(){
    string str1 = "xaybadfeg";
    string str2 = "abcdefg";
    LCS(str1,str2);
    getchar();
    return 0;
}

非常感谢任何输入。谢谢！

4

2 回答 2

1

“abdeg”是最长的公共子序列，但还有其他类似“abdfg”的子序列。

回溯是错误的。如果您输出 i 和 j 的值，那么它们将变为负数，然后访问无效的字符串索引。

从字符串索引中减去 1 应该会给出正确的答案。我也改变了|| && 的条件。

int i = str1.size(), j = str2.size();
std::string subSeqStr="";
while (i > 0 && j > 0){
    if (str2[j - 1] != str1[i - 1]) {
        if (out[i][j - 1] > out[i - 1][j])
            j--;
        else
            i--;
    }
    else{
        subSeqStr.insert(subSeqStr.begin(), str2[j - 1]);
        i--; j--;
    }
}
于 2016-07-09T20:37:40.413 回答
0

这看起来不对：

if (i == 0 || j == 0)
    out[i][j] = 0;

您的字符串从 0 开始索引，因此您不能应用大多数教科书和教程中出现的公式，因为它认为索引从 1 开始。

最简单的可能是在你的字符串前面加上一些东西，所以你的索引也从 1 开始。否则，你将不得不对公式做一些难看的修改。

于 2016-07-09T20:10:24.000 回答