[SOLVED] Longest common subsequence of more than 1 Letter in a string

Longest common subsequence of more than 1 Letter in a string

I'm trying to find the LCS of more than one letter in two strings using a k value. For example, if

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

then the LCS would be 4: "AAABBBDDDEEE" or "AAACCCDDDEEE", another example is if

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

then the LCS would be 2: "EEBB", "EEFF", "DDFF", "DDBB", ... and so on. How would I be able to do it so that more than one character is in each cell of the table and if the characters are not equal I would have to use a sort, i.e. "EF" == "FE"

Solution

Use std::is_permutation to find if two strings contain the same characters. To store more than one character in each "cell of the table" use std::string.

For any questions on c++, go here.

EDIT: Here is a demo of substr's usage:

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,]