#include #include #include #include using namespace std; bool solve(const string& A, const string& B, const string& C) { // possible[a][b] <==> A[a..] mix B[b..] == C[a+b..] vector< vector > possible( A.size()+1, vector(B.size()+1) ); // 動的計画法で possible[a][b] を埋める possible[A.size()][B.size()] = true; for(int b=B.size(),a=A.size()-1; a>=0; --a) possible[a][b] = (A[a]==C[a+b] && possible[a+1][b]); for(int a=A.size(),b=B.size()-1; b>=0; --b) possible[a][b] = (B[b]==C[a+b] && possible[a][b+1]); for(int b=B.size()-1; b>=0; --b) for(int a=A.size()-1; a>=0; --a) possible[a][b] = (A[a]==C[a+b] && possible[a+1][b] || B[b]==C[a+b] && possible[a][b+1]); // 欲しい答え return possible[0][0]; } int main() { int N; cin>>N; assert( 1<=N && N<=1000 ); for(int i=1; i<=N; ++i) { string A,B,C; cin>>A>>B>>C; assert( A.size() + B.size() == C.size() ); assert( 1<=A.size() && A.size()<=200 ); assert( 1<=B.size() && B.size()<=200 ); cout << "Data set " << i << ": " << (solve(A,B,C)?"yes":"no") << endl; } }