P12713 [KOI 2021 Round 1] 公共子序列扩展

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

对一个序列来说，删除其中的若干个元素（可能为 0 个）后所得到的新序列被称为它的“子序列”。例如，字符串 `aab` 是 $X =$ `ababca` 的子序列，但不是 $Y =$ `cbabba` 的子序列。 若两个序列中都包含某个子序列 $W$，则 $W$ 称为这两个序列的“公共子序列”。例如，在上述的 $X$ 和 $Y$ 中，`baa` 是它们的公共子序列，但 `aab` 不是。 现在，给定两个字符串 $X$ 和 $Y$，以及它们的一个公共子序列 $W$，我们想判断 $W$ 是否**可以扩展**。定义如下： - 若可以在 $W$ 的某个位置插入一个字符，使其仍然为 $X$ 和 $Y$ 的公共子序列，则称 $W$ 是“可扩展”的； - 否则，称其为“不可扩展”的。 例如，若 $W =$ `baa`，可以扩展为 `baba`，所以 $W$ 是可扩展的。但若 $W =$ `ca`，则无法再扩展。 请编写程序判断给定的 $W$ 是否可扩展。

第一行输入一个整数 $T$，表示测试用例数量。 接下来的 $3 \times T$ 行中，每 3 行描述一个测试用例，依次为： 第 1 行：字符串 $X$ 第 2 行：字符串 $Y$ 第 3 行：字符串 $W$

对每个测试用例，输出一行：若 $W$ 可扩展，输出 `1`；否则输出 `0`。

**约束条件** - 每组输入中包含 1 到 100 个测试用例 - 所有测试用例中，$|X|$ 的总长度不超过 200\,000，$|Y|$ 的总长度也不超过 200\,000 - $W$ 是 $X$ 和 $Y$ 的公共子序列 - 所有序列仅包含小写英文字母 **子任务** 1.（14 分）$|W| = 1$ 2.（17 分）$|X|$ 和 $|Y|$ 的总长度均不超过 300 3.（25 分）$|X|$ 和 $|Y|$ 的总长度均不超过 20\,000 4.（44 分）无附加约束条件