Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
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>
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 () |
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'
int main | ( | void | ) |
Main function (driver code)
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.
str1 | first string 'X' |
str2 | second string 'Y' |
|
static |
Test Function