字符串中超过 1 个字母的最长公共子序列

Question

我正在尝试使用 k 值在两个字符串中查找多个字母的 LCS。例如，如果

k  = 3 
s1 = "AAABBBCCCDDDEEE"  
s2 = "AAACCCBBBDDDEEE"

那么LCS就是4："AAABBBDDDEEE"或者"AAACCCDDDEEE"，另一个例子是if

k  = 2 
s1 = "EEDDFFAABBCC" 
s2 = "AACCDDEEBBFF"

那么 LCS 将是 2："EEBB"、"EEFF"、"DDFF"、"DDBB"、...等等。我将如何做到这一点，以便 table 的每个单元格中有多个字符，如果字符不相等，我将不得不使用排序，即 "EF" == "FE"

Answer 1

使用std::is_permutation判断两个字符串是否包含相同的字符。要在每个“table 的单元格”中存储多个字符，请使用 std::string.

如有任何关于 C++ 的问题，请转到 here。

编辑： 这是 substr 用法的演示：

std::string s{"AAABBBCCCDDD"};
std::cout << s.substr(3, 3) << std::endl; // BBB

std::vector<std::string> substr_table;
substr_table.reserve(4);                     // reserve space for elements

for(std::size_t i{}; i < s.size(); i += 3){  // break up s into four substrings
    substr_table.push_back(s.substr(i, 3));
}

std::cout << "[ ";
std::copy(
    substr_table.cbegin(), 
    substr_table.cend(), 
    std::ostream_iterator<std::string>(std::cout, ", ")
); // Print vector
std::cout << "]\n";
// OUTPUT: [ AAA, BBB, CCC, DDD,]

字符串中超过 1 个字母的最长公共子序列

Longest common subsequence of more than 1 Letter in a string

c++

algorithm

lcs