← 返回题目列表

Codeforces · 1366/G

G. 构造字符串

中文机器翻译题面 查看原题

让我们表示函数$$$f(s)$$$,它接受由小写拉丁字母和点组成的字符串$$$s$$$,并返回由小写拉丁字母组成的字符串,如下所示:

1. 设 $$$r$$$ 为空字符串;
2.从左到右处理$$$s$$$的字符。对于每个字符 $$$c$$$,执行以下操作:如果 $$$c$$$ 是小写拉丁字母,则在字符串 $$$r$$$ 末尾附加 $$$c$$$;否则,从 $$$r$$$ 中删除最后一个字符(如果在删除最后一个字符之前 $$$r$$$ 为空 — 函数崩溃);
3. 返回 $$$r$$$ 作为函数的结果。

给定两个字符串 $$$s$$$ 和 $$$t$$$。您必须从 $$$s$$$ 中删除尽可能少的字符,以便 $$$f(s) = t$$$ (并且该函数不会崩溃)。请注意,您不允许将新字符插入 $$$s$$$ 或对现有字符重新排序。

输入

输入由两行组成:第一行包含 $$$s$$$ — 由小写拉丁字母和点组成的字符串,第二行包含 $$$t$$$ — 由小写拉丁字母组成的字符串 ($$$1 \le |t| \le |s| \le 10000$$$)。

对输入的附加约束:可以从 $$$s$$$ 中删除一些字符,以便 $$$f(s) = t$$$。

输出

打印一个整数 — 您必须从 $$$s$$$ 中删除的最小字符数,这样 $$$f(s)$$$ 不会崩溃并返回 $$$t$$$ 作为函数的结果。

示例

输入 #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