Construct the String

题意翻译

## 题目描述 定义 $f(s)$ 为一个字符串函数，其接收的字符串中只包含小写字母和`.`。$f(s)$ 的作用方法为： 1. 初始状态 $r$ 为空字符串`""`。 2. 从左至右处理 $s$ 中的字符。如果当前字符为小写字母，则将其添加到 $r$ 的末尾；如果当前字符为`.`，则 删去 $r$ 的最后一个字符。特别的，如果当前 $r$ 为空，而当前字符为`.`，则函数会崩溃（输入字符串非法）。 3. 最终得到的 $r$ 即为函数的返回值。 对于给定的字符串 $s$ 和 $t$ ，你需要从 $s$ 中删去尽可能少的字符，使得 $f(s')=t$（$s'$必须是合法的输入字符串，也即，函数作用过程中不能发生崩溃）。 求最少要删除的字符数目。 ## 输入格式 输入分为两行。第一行为字符串 $s$ ，也即待删除的字符串；第二行为字符串 $t$ ，也即目标字符串。两个字符串的长度满足 $1\leq|t|\leq|s|\leq10000$，且保证对于给定的输入，一定存在合法的删除方式，使得 $f(s')=t$ 。 ## 输出格式 输出一个整数：使得 $f(s')=t$ 最少要删除的字符数目。

题目描述

Let's denote the function $ f(s) $ that takes a string $ s $ consisting of lowercase Latin letters and dots, and returns a string consisting of lowercase Latin letters as follows: 1. let $ r $ be an empty string; 2. process the characters of $ s $ from left to right. For each character $ c $ , do the following: if $ c $ is a lowercase Latin letter, append $ c $ at the end of the string $ r $ ; otherwise, delete the last character from $ r $ (if $ r $ is empty before deleting the last character — the function crashes); 3. return $ r $ as the result of the function. You are given two strings $ s $ and $ t $ . You have to delete the minimum possible number of characters from $ s $ so that $ f(s) = t $ (and the function does not crash). Note that you aren't allowed to insert new characters into $ s $ or reorder the existing ones.

输入输出格式

输入格式

The input consists of two lines: the first one contains $ s $ — a string consisting of lowercase Latin letters and dots, the second one contains $ t $ — a string consisting of lowercase Latin letters ( $ 1 \le |t| \le |s| \le 10000 $ ). Additional constraint on the input: it is possible to remove some number of characters from $ s $ so that $ f(s) = t $ .

输出格式

Print one integer — the minimum possible number of characters you have to delete from $ s $ so $ f(s) $ does not crash and returns $ t $ as the result of the function.

输入输出样例

输入样例 #1

a.ba.b.
abb

输出样例 #1

2

输入样例 #2

.bbac..a.c.cd
bacd

输出样例 #2

3

输入样例 #3

c..code..c...o.d.de
code

输出样例 #3

3