A6969 | 字符串混合
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
给定三个字符串 $A$、$B$ 和 $C$。已知 $C$ 的长度等于 $A$ 和 $B$ 的长度之和（即 $|C| = |A| + |B|$）。
字符串 $C$ 原本是由 $A$ 和 $B$ 按顺序交织而成的。也就是说，$C$ 可以通过以下过程生成：
1. 初始时，$C$ 为空串。
2. 每次操作，你可以选择 $A$ 或 $B$ 的首字符，将其移除并追加到 $C$ 的末尾。
3. 重复步骤 2，直到 $A$ 和 $B$ 都变为空串。
但是，现在的字符串 $C$ 并不是完美的。在交织生成后，$C$ 中的某些字符被修改了。
你的任务是计算：为了让 $C$ 变回一个由 $A$ 和 $B$ 合法交织而成的字符串，最少需要修改 $C$ 中的多少个字符？
字符串 $C$ 原本是由 $A$ 和 $B$ 按顺序交织而成的。也就是说，$C$ 可以通过以下过程生成：
1. 初始时，$C$ 为空串。
2. 每次操作，你可以选择 $A$ 或 $B$ 的首字符，将其移除并追加到 $C$ 的末尾。
3. 重复步骤 2，直到 $A$ 和 $B$ 都变为空串。
但是，现在的字符串 $C$ 并不是完美的。在交织生成后，$C$ 中的某些字符被修改了。
你的任务是计算：为了让 $C$ 变回一个由 $A$ 和 $B$ 合法交织而成的字符串，最少需要修改 $C$ 中的多少个字符？
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 1000$)，表示测试数据的组数。
接下来对于每组数据：
- 第一行包含一个字符串 $A$ ($1 \le |A| \le 1000$)。
- 第二行包含一个字符串 $B$ ($1 \le |B| \le 1000$)。
- 第三行包含一个字符串 $C$ ($|C| = |A| + |B|$)。
所有字符串均由小写英文字母组成。
保证所有测试数据的 $|A|$ 之和不超过 $2000$， $|B|$ 之和不超过 $2000$。
接下来对于每组数据：
- 第一行包含一个字符串 $A$ ($1 \le |A| \le 1000$)。
- 第二行包含一个字符串 $B$ ($1 \le |B| \le 1000$)。
- 第三行包含一个字符串 $C$ ($|C| = |A| + |B|$)。
所有字符串均由小写英文字母组成。
保证所有测试数据的 $|A|$ 之和不超过 $2000$， $|B|$ 之和不超过 $2000$。
输出格式
对于每组数据，输出一个整数，表示最少需要修改的字符数量。
输入输出样例
输入 #1
7 a b cb ab cd acbd ab ba aabb xxx yyy xyxyxy a bcd decf codes horse codeforces egg annie egaegaeg
输出 #1
1 0 2 0 3 2 3
提示
样例 1 解释
$A=\text{"a"}, B=\text{"b"}, C=\text{"cb"}$。
合法的交织结果只能是 "ab" 或 "ba"。
- 变成 "ab": 需要修改 $C[0]$ ('c'-\>'a'), $C[1]$ ('b'-\>'b' 不变)，共 1 次。
- 变成 "ba": 需要修改 $C[0]$ ('c'-\>'b'), $C[1]$ ('b'-\>'a'), 共 2 次。
最少需要修改 1 次。
数据范围
- $1 \le T \le 1000$
- $\sum |A|, \sum |B| \le 2000$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？