# Shortest Common Super Sequence

Given two strings, you have to find the shortest common super sequence between them and print the length of the super sequence.

Input:
T Test case
T no of input string will be given to you.
E.g.
3
abcd abxy
sghk rfgh
svd vjhfd
Constrain
1≤ length (string1) ≤100
1≤ length (string2) ≤100
Output:
Print the length of the shortest super sequence formed from these two strings.

**Example**

T=3
Input:
abcd abxy
Output:
6 (abcdxy)
Input:
sghk rfgh
Output:
6 (srfghk)
Input:
svd vjhfd
Output:
6 (svjhfd)

**Explanation with example:**

Let there are two strings str1 and str2.

str1 = "abcd"
str2 = "abxy"

To find out the length of the super sequence from these two string is a bit difficult. To solve this problem we have to follow these steps:

- We have to find out the longest common subsequence between the two strings. From "abcd" and "abxy" the longest common subsequence is "ab".
- After getting the longest common subsequence we will add the non-common elements with the longest common subsequence. Non-common characters from "abcd" is "cd" and from "abxy" is "xy".
- Therefore the length of the shortest common super sequence is:

**length of the two strings-length of the longest common subsequencs**

The length of the shortest common super sequence is **6 (abcdxy)**

Using a dynamic programming algorithm to find out the longest common subsequence between two given string is very efficient and fast as compared to the recursion approach.

Let f(a,b) = count the number of common subsequences from the two string starting from 0 to position a and starting from 0 to position b.

**Considering the two facts:**

- If the character of string1 at index a and character of string1 at index b are the same then we have to count how many characters are the same between the two strings before these indexes? Therefore,

**f(a,b)=f(a-1,b-1)+1**

- If the character of string1 at index a and character of string1 at index b are not same then we have to calculate the maximum common character count between (0 to a-1 of string1 and 0 to b of string2) and (0 to a of string1 and 0 to b-1 of string2).

**f(a,b)=max((f(a-1,b),f(a,b-1))**

For the two strings:

str1 = "abcd"
str2 = "abxy"

Recursive algorithm:DP conversion:C++ Implementation:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput