Shortest Common Supersequence

You are given two strings str1 and str2 of lengths \(n\) and \(m\) respectively. Your task is to find the length of the shortest common supersequence (SCS) of these two strings.

A supersequence of a string is a sequence that contains the string as a subsequence. In other words, a string s is a supersequence of another string t if t can be derived from s by deleting some (possibly zero) characters without changing the order of the remaining characters.

You need to determine the minimum length of a string that has both str1 and str2 as subsequences.

Example:

• For str1 = "abc" and str2 = "ac", one shortest common supersequence is "abc" with a length of 3.
• For str1 = "geek" and str2 = "eke", one shortest common supersequence is "geeke" with a length of 5.

The problem can be solved using dynamic programming. One common approach is to formulate a recurrence relation for the problem as follows:

\[ \text{dp}[i][j] = \begin{cases} j & \text{if } i = 0 \\ i & \text{if } j = 0 \\ 1 + \text{dp}[i-1][j-1] & \text{if } str1[i-1] = str2[j-1] \\ 1 + \min(\text{dp}[i-1][j], \text{dp}[i][j-1]) & \text{if } str1[i-1] \neq str2[j-1] \end{cases} \]

inputFormat

The input is given via stdin and consists of two lines:

• The first line contains the string str1.
• The second line contains the string str2.

outputFormat

Output a single integer representing the length of the shortest common supersequence of str1 and str2.

The output should be written to stdout.

## sample

abc
ac

3