search

TheAlgorithms / C-Plus-Plus

Collection of various algorithms in mathematics, machine learning, computer science and physics implemented in C++ for educational purposes.
https://thealgorithms.github.io/C-Plus-Plus
MIT License
30.73k stars 7.28k forks source link

[FEATURE]: Shortest Common Supersequence #1029

Closed ridhishjain-zepto closed 4 years ago

ridhishjain-zepto commented 4 years ago

Detailed Description

Definition: The Shortest Common Supersequence (SCS) is a string Z which is the shortest supersequence of two given strings X and Y (which may not be continuously present in Z, but order must be maintained).

example 1: X: 'ABCXYZ', Y: 'ABZ' then Z will be 'ABCXYZ' (y is not continuous but in order)

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

Context

Besides LCS, we need an algorithm for finding shortest common supersequence

Possible Implementation

Implementation can be done using DP lookup table method

ridhishjain-zepto commented 4 years ago

thoughts @Panquesito7?