题意

给定一个字符串 $t$，我们需要判断是否可以通过不超过两个子序列（即从原串 $s$ 中取出两个不相交的子序列）得到 $t$。
换句话说，$t$ 可以拆分成 $a + b$，其中 $a$ 是第一个子序列，$b$ 是第二个子序列。一般情况 $a$ 可以为空。

思路

枚举 $a$ 的所有可能长度（$0 \le |a| < |s|$），然后检查对于每一对 $a$ 和 $b$ 是否存在解。
我们需要判断：$s$ 中是否包含 $a$ 和 $b$ 作为子序列，并且这两个子序列在 $s$ 中的位置不相交。

最初可以设计如下 DP：
设 $dp[lens][lena][lenb]$ 为布尔值，表示 $s$ 的前 $lens$ 个字符中，是否包含 $a$ 的前 $lena$ 个字符和 $b$ 的前 $lenb$ 个字符作为不相交的子序列。
转移很简单：如果 $dp[lens][lena][lenb] = 1$，我们可以跳过 $s[lens]$（$0$ 索引），更新 $dp[lens+1][lena][lenb]$；
如果 $s[lens] = a[lena]$，则更新 $dp[lens+1][lena+1][lenb]$；
如果 $s[lens] = b[lenb]$，则更新 $dp[lens+1][lena][lenb+1]$。
但这个 DP 的复杂度是 $O(|s|^3)$。

我们可以优化：将 $lens$ 作为 DP 的值，而不是布尔值。
即维护 $dp[lena][lenb]$ 表示达到当前状态所需的最小的 $lens$。
但问题在于如何定义转移。

注意到一个事实：假设当前 $lens = dp[lena][lenb]$，我们想向 $a$ 中添加下一个字符 $a[lena]$。
最优策略是选择 $s[lens \dots |s|)$ 中第一个出现 $a[lena]$ 的位置。
可以用反证法证明：如果第一个出现的位置是空闲的，那么取它是最优的；如果第一个出现的位置会被 $b$ 占用，那么这种情况会由另一个状态 $dp[lena][len'_b]$（其中 $len'_b > lenb$）来处理。

增加 $lenb$ 的逻辑类似。
因此，我们需要在枚举 $a$ 和 $b$ 之前，预处理数组 $nxt[pos][c]$，表示在 $s$ 的后缀 $pos$ 中字符 $c$ 下一次出现的位置。
之后每次转移时使用该数组，复杂度降为 $O(|s|^2)$。

算法步骤

1. 枚举 $a$ 的长度 $len_a$（$0 \le len_a < |s|$），令 $a = t[0 \dots len_a-1]$，$b = t[len_a \dots |t|-1]$。
2. 预处理 $nxt[pos][c]$ 数组，表示从 $s$ 的第 $pos$ 个位置开始，字符 $c$ 下一次出现的位置（$0$ 索引）。
3. 初始化 $dp[0][0] = 0$，其余为无穷大。
4. 按顺序遍历 $lena$ 和 $lenb$，使用 $nxt$ 数组进行转移：
   • 如果 $lena < |a|$，则 $dp[lena+1][lenb] = \min(dp[lena+1][lenb], nxt[dp[lena][lenb]][a[lena]] + 1)$
   • 如果 $lenb < |b|$，则 $dp[lena][lenb+1] = \min(dp[lena][lenb+1], nxt[dp[lena][lenb]][b[lenb]] + 1)$
5. 如果最终 $dp[|a|][|b|] \le |s|$，则存在解。
6. 如果所有枚举都不存在解，则输出无解。

复杂度分析

• 预处理 $nxt$ 数组：$O(|s| \times 26)$
• 对于每个 $a$ 的长度，DP 状态数为 $O(|a| \times |b|) = O(|t|^2)$，转移为 $O(1)$
• 总复杂度：$O(|s| \times |t|^2)$，最坏情况下 $O(|s|^3)$

代码说明

• 使用二维数组 $dp$ 存储最小前缀长度，初始化为一个大数（如 $|s|+1$）。
• 使用 $nxt$ 数组快速找到下一个字符的位置，避免线性扫描。
• 外层循环枚举 $a$ 的长度，内层进行 DP 转移。
• 最终检查 $dp[|a|][|b|]$ 是否小于等于 $|s|$，若是则输出 YES，否则继续枚举。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 805;
int f[MAXN][MAXN];
bool check(string s,string t1,string t2){
	memset(f,-1,sizeof(f));
	f[0][0] = 0;
	s = '0' + s;
	t1 = '0' + t1;
	t2 = '0' + t2;
	for(int i=0; i<s.size(); i++){
		for(int j=0; j<t1.size(); j++){
			if(f[i][j] == -1)	continue;
			f[i+1][j] = max(f[i+1][j],f[i][j]);
			if(s[i+1] == t1[j+1])	f[i+1][j+1] = max(f[i+1][j+1],f[i][j]);
			if(s[i+1] == t2[f[i][j] + 1])	f[i+1][j] = max(f[i+1][j],f[i][j] + 1); 
		}
	}
	if(f[s.size()-1][t1.size()-1] == t2.size()-1)
		return true;
	return false; 
}
bool solve(string s,string t){
	for(int i=0; i<=t.size(); i++){
		string t1,t2;
		for(int j=0; j<i; j++){
			t1 = t1 + t[j];
		}
		for(int j=i; j<t.size(); j++){
			t2 = t2 + t[j];
		}
		if(check(s,t1,t2))
			return true;	
	}
	return false;
}
int main(){
	int n;
	cin>>n;
	while(n--){
		string s,t;
		cin>>s>>t;
		if(solve(s,t)){
			printf("YES\n");
		}
		else{
			printf("NO\n");
		}
	}
	return 0;
}