Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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)

164 {
165 // test for implementation
166 test();
167
168 // user input
169 std::string s1, s2;
170 std::cin >> s1;
171 std::cin >> s2;
172
173 std::string ans;
174
175 // user output
177 std::cout << ans;
178 return 0;
179}
static void test()
Definition shortest_common_supersequence.cpp:124
std::string scs(const std::string &str1, const std::string &str2)
Definition shortest_common_supersequence.cpp:42
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
str1first string 'X'
str2second string 'Y'
Returns
string 'Z', superSequence of X and Y
42 {
43
44 // Edge cases
45 // If either str1 or str2 or both are empty
46 if(str1.empty() && str2.empty()) {
47 return "";
48 }
49 else if(str1.empty()) {
50 return str2;
51 }
52 else if(str2.empty()) {
53 return str1;
54 }
55
56 // creating lookup table
57 std::vector <std::vector <int>> lookup(str1.length() + 1, std::vector <int> (str2.length() + 1, 0));
58
59 for(int i=1; i <= str1.length(); i++) {
60 for(int j=1; j <= str2.length(); j++) {
61 if(str1[i-1] == str2[j-1]) {
62 lookup[i][j] = lookup[i-1][j-1] + 1;
63 }
64 else {
65 lookup[i][j] = std::max(lookup[i-1][j], lookup[i][j-1]);
66 }
67 }
68 }
69
70 // making supersequence
71 // i and j are initially pointed towards end of strings
72 // Super-sequence will be constructed backwards
73 int i=str1.length();
74 int j=str2.length();
76
77 while(i>0 && j>0) {
78
79 // If the characters at i and j of both strings are same
80 // We only need to add them once in s
81 if(str1[i-1] == str2[j-1]) {
82 s.push_back(str1[i-1]);
83 i--;
84 j--;
85 }
86 // otherwise we check lookup table for recurrences of characters
87 else {
88 if(lookup[i-1][j] > lookup[i][j-1]) {
89 s.push_back(str1[i-1]);
90 i--;
91 }
92 else {
93 s.push_back(str2[j-1]);
94 j--;
95 }
96 }
97 }
98
99 // copying remaining elements
100 // if j becomes 0 before i
101 while(i > 0) {
102 s.push_back(str1[i-1]);
103 i--;
104 }
105
106 // if i becomes 0 before j
107 while(j > 0) {
108 s.push_back(str2[j-1]);
109 j--;
110 }
111
112 // As the super sequence is constructd backwards
113 // reversing the string before returning gives us the correct output
114 reverse(s.begin(), s.end());
115 return s;
116 }
T begin(T... args)
T empty(T... args)
T end(T... args)
T max(T... args)
T push_back(T... args)
T reverse(T... args)
T length(T... args)
Here is the call graph for this function:

◆ test()

static void test ( )
static

Test Function

Returns
void
124 {
125 // custom input vector
126 std::vector <std::vector <std::string>> scsStrings {
127 {"ABCXYZ", "ABZ"},
128 {"ABZ", "ABCXYZ"},
129 {"AGGTAB", "GXTXAYB"},
130 {"X", "Y"},
131 };
132
133 // calculated output vector by scs function
134 std::vector <std::string> calculatedOutput(4, "");
135 int i=0;
136 for(auto & scsString : scsStrings) {
137
139 scsString[0], scsString[1]
140 );
141 i++;
142 }
143
144 // expected output vector acc to problem statement
145 std::vector <std::string> expectedOutput {
146 "ABCXYZ",
147 "ABCXYZ",
148 "AGGXTXAYB",
149 "XY"
150 };
151
152 // Testing implementation via assert function
153 // It will throw error if any of the expected test fails
154 // Else it will give nothing
155 for(int i=0; i < scsStrings.size(); i++) {
156 assert(expectedOutput[i] == calculatedOutput[i]);
157 }
158
159 std::cout << "All tests passed successfully!\n";
160 return;
161}