Minimum Deletions to Form Subsequence

Given two strings (s) and (t), your task is to remove the minimum number of characters from (s) such that (t) becomes a subsequence of the resulting string. A subsequence of a string is obtained by deleting zero or more characters without changing the order of the remaining characters.

Formally, let (|s|) be the length of (s) and let (LCS(s,t)) be the length of the longest common subsequence between (s) and (t). The answer is given by: [ \text{Answer} = |s| - LCS(s,t) ]

If it is impossible to obtain (t) as a subsequence, the function will return (|s|) (i.e. delete all characters).

Input strings consist of ASCII characters. Make sure your solution reads from standard input and writes to standard output.

inputFormat

The input consists of two lines. The first line contains the string (s) and the second line contains the string (t).

outputFormat

Output a single integer representing the minimum number of characters that need to be deleted from (s) so that (t) becomes a subsequence of (s).## sample

abcde
ace

2