Shortest Uncommon Subsequence

Time limit2sMemory limit128 MB

Summary

Given two strings, compute the length of the shortest subsequence of A that is not a subsequence of B.

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

Problem

A subsequence of string A is made by choosing one or more characters from A and writing them in their original relative order. The chosen characters do not have to be adjacent.

Given two strings A and B, find the length of the shortest string that is a subsequence of A but is not a subsequence of B.

Input

The first line contains string A, and the second line contains string B. Both strings consist only of lowercase English letters, and each length is at most 1000. Every input is guaranteed to have an answer.

Output

Print the length of the shortest string that is a subsequence of A but not a subsequence of B.

Examples3

Example 1
Input
```
ababaa
abbaa
```
Expected output
```
3
```
Example 2
Input
```
babab
babba
```
Expected output
```
3
```
Example 3
Input
```
banana
anbnaanbaan
```
Expected output
```
5
```