Skip to content

Files

Latest commit

Felix Rillingtrekhleb
Felix Rilling
and
Jun 12, 2018
5734e0a · Jun 12, 2018

History

History
This branch is 73 commits behind trekhleb/javascript-algorithms:master.

shortest-common-supersequence

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Apr 27, 2018
Apr 27, 2018
Jun 12, 2018

Shortest Common Supersequence

The shortest common supersequence (SCS) of two sequences X and Y is the shortest sequence which has X and Y as subsequences.

In other words assume we're given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.

This is a problem closely related to the longest common subsequence problem.

Example

Input:   str1 = "geek",  str2 = "eke"
Output: "geeke"

Input:   str1 = "AGGTAB",  str2 = "GXTXAYB"
Output:  "AGXGTXAYB"

References