Shortest string containing both

Interview

Time limit1sMemory limit256 MB

Summary

Find the length of the shortest string that has both given strings as subsequences.

Level: Medium4 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

You are given two strings A and B.

A string X is a subsequence of a string S if you can delete zero or more characters from S and join the remaining characters, in their original order, to get X.

Write a program that computes the length of the shortest string S that has both A and B as subsequences.

For example, if A = "abcbdab" and B = "bdcaba", then S = "abdcabdab" has both of them as subsequences, and no S shorter than 9 works.

Input

The first line contains the string A and the second line contains the string B. Both strings consist of lowercase letters only, and each has length between 1 and 1,000.

Output

Print the length of the shortest string that has both A and B as subsequences.

Examples3

Example 1
Input
```
abcbdab
bdcaba
```
Expected output
```
9
```
Example 2
Input
```
programming
gaming
```
Expected output
```
11
```
Example 3
Input
```
abc
abc
```
Expected output
```
3
```