CF1989B Substring and Subsequence

题目描述

给定两个字符串 $a$ 和 $b$，均由小写拉丁字母组成。

一个字符串的子序列是指可以通过从原字符串中删除若干（可能为零）个字符后得到的字符串。一个字符串的子串是该字符串的一个连续子序列。

例如，考虑字符串 abac：

• a、b、c、ab、aa、ac、ba、bc、aba、abc、aac、bac 和 abac 是它的子序列；
• a、b、c、ab、ba、ac、aba、bac 和 abac 是它的子串。

你的任务是计算一个字符串的最小可能长度，使得该字符串包含 $a$ 作为子串，并且包含 $b$ 作为子序列。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。

每个测试用例的第一行包含一个字符串 $a$（$1 \le |a| \le 100$），由小写拉丁字母组成。

每个测试用例的第二行包含一个字符串 $b$（$1 \le |b| \le 100$），由小写拉丁字母组成。

输出格式

对于每个测试用例，输出一个整数，表示满足条件的字符串的最小可能长度。

输入输出样例 #1

输入 #1

5
aba
cb
er
cf
mmm
mmm
contest
test
cde
abcefg

输出 #1

4
4
3
7
7

说明/提示

在下面的示例中，与 $b$ 相等的子序列对应的字符用加粗表示。

在第一个示例中，其中一个可能的答案是 caba。

在第二个示例中，其中一个可能的答案是 ercf。

在第三个示例中，其中一个可能的答案是 mmm。

在第四个示例中，其中一个可能的答案是 contest。

在第五个示例中，其中一个可能的答案是 abcdefg。

由 ChatGPT 4.1 翻译