Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
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

 dynamic_programming
 Dynamic Programming algorithms.
 
 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 
174 
175  // user output
177  std::cout << ans;
178  return 0;
179 }
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();
75  std::string s;
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  }
Here is the call graph for this function:

◆ test()

static void test ( )
static

Test Function

Returns
void
124  {
125  // custom input vector
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 }
test
static void test()
Definition: shortest_common_supersequence.cpp:124
std::string
STL class.
std::vector
STL class.
std::string::length
T length(T... args)
ans
ll ans(ll n)
Definition: matrix_exponentiation.cpp:91
dynamic_programming::shortest_common_supersequence::scs
std::string scs(const std::string &str1, const std::string &str2)
Definition: shortest_common_supersequence.cpp:42
std::reverse
T reverse(T... args)
std::string::push_back
T push_back(T... args)
std::cout
std::string::begin
T begin(T... args)
std::string::empty
T empty(T... args)
std::string::end
T end(T... args)
std::max
T max(T... args)
std::cin