shortest_common_supersequence.cpp File Reference

SCS is a string Z which is the shortest supersequence of strings X and Y (may not be continuous in Z, but order is maintained). More...

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cassert>

Include dependency graph for shortest_common_supersequence.cpp:

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.
namespace	shortest_common_supersequence
	Shortest Common Super Sequence algorithm.

Functions
std::string	dynamic_programming::shortest_common_supersequence::scs (const std::string &str1, const std::string &str2)
static void	test ()
int	main ()

Detailed Description

SCS is a string Z which is the shortest supersequence of strings X and Y (may not be continuous in Z, but order is maintained).

The idea is to use lookup table method as used in LCS. For example: example 1:- X: 'ABCXYZ', Y: 'ABZ' then Z will be 'ABCXYZ' (y is not continuous but in order)

For example: example 2:- X: 'AGGTAB', Y: 'GXTXAYB' then Z will be 'AGGXTXAYB'

Author

Ridhish Jain

See also

more on SCS

related problem Leetcode

Function Documentation

main()

int main

(

void

)

Main function (driver code)

           {
    // test for implementation
    test();
 
    // user input
    std::string s1, s2;
    std::cin >> s1;
    std::cin >> s2;
 
    std::string ans;
 
    // user output
    ans = dynamic_programming::shortest_common_supersequence::scs(s1, s2);
    std::cout << ans;
    return 0;
}

Here is the call graph for this function:

scs()

std::string dynamic_programming::shortest_common_supersequence::scs	(	const std::string &	str1,
		const std::string &	str2
	)

Function implementing Shortest Common Super-Sequence algorithm using look-up table method.

Parameters

str1	first string 'X'
str2	second string 'Y'

Returns

string 'Z', superSequence of X and Y

                                                                    {
 
            // Edge cases
            // If either str1 or str2 or both are empty
            if(str1.empty() && str2.empty()) {
                return "";
            }
            else if(str1.empty()) {
                return str2;
            }
            else if(str2.empty()) {
                return str1;
            }
 
            // creating lookup table
            std::vector <std::vector <int>> lookup(str1.length() + 1, std::vector <int> (str2.length() + 1, 0));
      
            for(int i=1; i <= str1.length(); i++) {
                for(int j=1; j <= str2.length(); j++) {
                    if(str1[i-1] == str2[j-1]) {
                        lookup[i][j] = lookup[i-1][j-1] + 1;
                    }
                    else {
                        lookup[i][j] = std::max(lookup[i-1][j], lookup[i][j-1]);
                    }
                }
            }
 
            // making supersequence
            // i and j are initially pointed towards end of strings
            // Super-sequence will be constructed backwards
            int i=str1.length();
            int j=str2.length();
            std::string s;
      
            while(i>0 && j>0) {
 
                // If the characters at i and j of both strings are same
                // We only need to add them once in s
                if(str1[i-1] == str2[j-1]) {
                    s.push_back(str1[i-1]);
                    i--;
                    j--;
                }
                // otherwise we check lookup table for recurrences of characters
                else {
                    if(lookup[i-1][j] > lookup[i][j-1]) {
                        s.push_back(str1[i-1]);
                        i--;
                    }
                    else {
                        s.push_back(str2[j-1]);
                        j--;
                    }
                }
            }
 
            // copying remaining elements
            // if j becomes 0 before i
            while(i > 0) {
                s.push_back(str1[i-1]);
                i--;
            }
 
            // if i becomes 0 before j
            while(j > 0) {
                s.push_back(str2[j-1]);
                j--;
            }
 
            // As the super sequence is constructd backwards
            // reversing the string before returning gives us the correct output  
            reverse(s.begin(), s.end());
            return s;
        }

Here is the call graph for this function:

test()

static void test ( )

static

Test Function

Returns

void

                   {
    // custom input vector
    std::vector <std::vector <std::string>> scsStrings {
        {"ABCXYZ", "ABZ"},
        {"ABZ", "ABCXYZ"},
        {"AGGTAB", "GXTXAYB"},
        {"X", "Y"},
    };
 
    // calculated output vector by scs function
    std::vector <std::string> calculatedOutput(4, "");
    int i=0;
    for(auto & scsString : scsStrings) {
        
        calculatedOutput[i] = dynamic_programming::shortest_common_supersequence::scs(
            scsString[0], scsString[1]
        );
        i++;
    }
 
    // expected output vector acc to problem statement
    std::vector <std::string> expectedOutput {
        "ABCXYZ",
        "ABCXYZ",
        "AGGXTXAYB",
        "XY"
    };
 
    // Testing implementation via assert function
    // It will throw error if any of the expected test fails
    // Else it will give nothing
    for(int i=0; i < scsStrings.size(); i++) {
        assert(expectedOutput[i] == calculatedOutput[i]);
    }
 
    std::cout << "All tests passed successfully!\n";
    return;
}