shortest-common-supersequence

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

• GeeksForGeeks