题目内容

给定一个目标字符串 $T$ 和一个源字符串 $S$，请你找出需要在 $S$ 中最少插入多少个字符（可以在任意位置插入），才能使得 $T$ 成为 $S$ 的子序列。

注意：

1. 子序列定义：对于一个字符串 $U$，如果字符串 $V$ 可以通过删除 $U$ 中的一些字符（可以删除 $0$ 个或多个，不改变剩余字符的相对顺序）得到，则称 $V$ 是 $U$ 的子序列。
   • 例如：在 "$acbd$" 中，"$ab$"、"$ac$"、"$ad$"、"$cd$"、"$abcd$"等都是其子序列。
   • 子序列中的字符在原字符串中不需要连续出现，但必须保持原有的相对顺序。
   • 例如："$ab$" 是 "$axby$" 的子序列，因为 '$a$' 在 '$b$' 之前出现。
2. 只能插入字符，不能删除或修改现有字符。
3. 插入的字符必须是 $T$ 中有的字符。

约束条件

• $1 \le |S|, |T| \le 2500$
• $S$ 和 $T$ 只包含小写字母 $'a'$~$'z'$

输入描述

第一行输入目标字符串 $T$

第二行输入源字符串 $S$

输出描述

输出最少需要插入的字符数量

样例1

输入

abc
ac

输出

1

说明

在 '$c$' 前面插入 '$b$'，得到 "$abc$"，所以需要插入 $1$ 个字符。这是最典型的情况，展示了当目标字符串只比源字符串多一个字符时如何处理。

样例2

输入

abc
xyz

输出

3

说明

源字符串 $S$ 中没有目标字符串 $T$ 的任何字符，需要插入 "$abc$" 全部 $3$ 个字符。这是边界情况，展示了当两个字符串完全不相交时如何处理。

样例3

输入

aaab
ab

输出

2

说明

源字符串 $S$ 只有 "$ab$"，而目标字符串 $T$ 有三个 '$a$' 和一个 '$b$'。可以匹配一个 '$a$' 和一个 '$b$'，但还需要插入两个 '$a$'。这是特殊情况，展示了重复字符的处理。