A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/d7/d65/shortest__common__supersequence_8cpp_source.html below:

TheAlgorithms/C++: dynamic_programming/shortest_common_supersequence.cpp Source File

Go to the documentation of this file. 42

std::string

scs

(

const

std::string &str1,

const

std::string &str2) {

46 if

(str1.empty() && str2.empty()) {

49 else if

(str1.empty()) {

52 else if

(str2.empty()) {

57

std::vector <std::vector <int>> lookup(str1.length() + 1, std::vector <int> (str2.length() + 1, 0));

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;

65

lookup[i][j] = std::max(lookup[i-1][j], lookup[i][j-1]);

81 if

(str1[i-1] == str2[j-1]) {

82

s.push_back(str1[i-1]);

88 if

(lookup[i-1][j] > lookup[i][j-1]) {

89

s.push_back(str1[i-1]);

93

s.push_back(str2[j-1]);

102

s.push_back(str1[i-1]);

108

s.push_back(str2[j-1]);

114

reverse(s.begin(), s.end());

126

std::vector <std::vector <std::string>> scsStrings {

127

{

"ABCXYZ"

,

"ABZ"

},

128

{

"ABZ"

,

"ABCXYZ"

},

129

{

"AGGTAB"

,

"GXTXAYB"

},

134

std::vector <std::string> calculatedOutput(4,

""

);

136 for

(

auto

& scsString : scsStrings) {

139

scsString[0], scsString[1]

145

std::vector <std::string> expectedOutput {

155 for

(

int

i=0; i < scsStrings.size(); i++) {

156

assert(expectedOutput[i] == calculatedOutput[i]);

159

std::cout <<

"All tests passed successfully!\n"

;

Dynamic Programming algorithms.

Shortest Common Super Sequence algorithm.

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

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4