题目内容

给定一个目标字符串 $T$ 和一个源字符串 $S$。你可以在 $S$ 的任意位置插入若干字符，每次插入的字符必须属于 $T$ 中的字符集合。在操作过程中，不能删除或修改 $S$ 中已有的字符。

现在需要通过对 $S$ 进行最少的插入操作，使得 $T$ 成为操作后 $S$ 的子序列。请计算最少需要插入多少个字符。

若字符串 $B$ 可以通过删除字符串 $A$ 中的0个或多个字符得到，且删除后剩余字符的相对顺序保持不变，则称 $B$ 是 $A$ 的子序列。

约束条件：

• $|S|$ 和 $|T|$ 均不小于 1，且不超过 2500。
• $S$ 和 $T$ 只包含小写字母。

输入描述

第一行包含一个字符串 $T$，表示目标字符串。

第二行包含一个字符串 $S$，表示源字符串。

输出描述

输出一个整数，表示需要插入到 $S$ 中的最少字符数量。

样例1

输入

abc
abc

输出

0

说明

目标串 $T$ 为 abc，源串 $S$ 也为 abc。$S$ 已经包含完整的 $T$ 作为子序列，最少插入次数为 0。

样例2

输入

aaa
a

输出

2

说明

向 $S$ 中插入 2 个 a。最少插入次数为 2。

样例3

输入

bca
abc

输出

1

说明

在 T 末尾插入一个a，最少插入次数为 1。

样例3

输入

datastructureandalgorithm
dtaastrucalgorithmandure

输出

8

说明

结果字符串为：dtatastructureandalgorithmandure

插入的字符：dta >t< astruc >tureand< algorithmandure

最少插入次数为 8 。