交错相互

问题描述

给定三个字符串，判断第三个字符串是否能由前两个字符串的字符交替组合而成，且保持每个原字符串内部的字符顺序不变。

输入格式

• 第一行包含一个正整数$n$（$1 \leq n \leq 1000$），表示测试用例数量
• 接下来$n$行，每行给出三个由大小写字母组成的字符串

输出格式

• 对于每个测试用例，输出Data set x: yes或Data set x: no，其中$x$为测试用例编号

示例

输入样例 1

3
cat tree tcraete
cat tree catrtee
cat tree cttaree

输出样例 1

Data set 1: yes
Data set 2: yes
Data set 3: no

约束条件

• 第三个字符串的长度严格等于前两个字符串长度之和
• 前两个字符串的长度在$1$到$200$个字符之间

示例说明

1. 有效案例

   • 字符串A: cat，字符串B: tree，字符串C: tcraete
     交替组合方式：t(B) → c(A) → r(B) → a(A) → e(B) → t(A) → e(B)
   • 字符串A: cat，字符串B: tree，字符串C: catrtee
     交替组合方式：完全使用A后接B的剩余字符

2. 无效案例

   • 字符串C: cttaree无法通过交替组合cat和tree生成
     矛盾点：第三个字符t需来自A，但此时A的第二个字符应为a

数据来源

Pacific Northwest 2004