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

  1. Input:   str1 = "geek",  str2 = "eke"
  2. Output: "geeke"
  4. Input:   str1 = "AGGTAB",  str2 = "GXTXAYB"
  5. Output:  "AGXGTXAYB"

References