DjvuLee

//@pku DY问题 
//自底向上的迭代 通过了
#include<iostream>
#include<string>
#include<fstream>
using namespace std;

#define N 210
#define fin cin
bool flag[N][N];
string s1,s2,s;
int main()
{
    //ifstream fin("input.txt");
    int num;
    while(fin>>num){
        for(int t=1;t<=num;t++)
        {
            fin>>s1>>s2>>s;                    
            for(int j=1;j<=s2.size();j++)
            {
                string sub=s2.substr(0,j);//s2的前j个字符
                string subs=s.substr(0,j);
                flag[0][j]= sub==subs ? true : false ;
            }
            for(int i=1;i<=s1.size();i++)
            {
                string sub=s1.substr(0,i);//s1的前i个字符
                string subs=s.substr(0,i);
                flag[i][0]= sub==subs ? true : false;
            }

            //i,j表示个数
            for(int i=1;i<=s1.size();i++)
                for(int j=1;j<=s2.size();j++)                    
                    if( (flag[i-1][j] && s[i+j-1]==s1[i-1]) || (flag[i][j-1] && s[i+j-1]==s2[j-1]) )
                        flag[i][j]=true;
                    else
                        flag[i][j]=false;
                
            if(flag[s1.size()][s2.size()])
                cout<<"Data set "<<t<<": yes"<<endl;
            else
                cout<<"Data set "<<t<<": no"<<endl;            
        }
    }//end while

    return 0;
}

//@pku DY
//备忘录方式
//程序理论上没有错误，但是TLE
#include<iostream>
#include<fstream>
#include<string>
using namespace std;

#define N 210
#define fin cin
bool flag[N][N];
string s1,s2,s;
bool dp(int pos1, int pos2, int pos);
int main()
{
    //ifstream fin("input.txt");
    int num;
    while(fin>>num){
        for(int t=1;t<=num;t++)
        {
            fin>>s1>>s2>>s;
            for(int i=0;i<N;i++)//s1,s2的下标都从0开始
                for(int j=0;j<N;j++)
                        flag[i][j]=false;
            
            bool res=dp(s1.size()-1,s2.size()-1,s.size()-1);
            if(res)
                cout<<"Data set "<<t<<": yes"<<endl;
            else
                cout<<"Data set "<<t<<": no"<<endl;
        }
    }//end while

    return 0;
}

bool dp(int pos1, int pos2, int pos)
{
    if(pos2==-1)//边界值
    {
        string sub1=s1.substr(0,pos1+1);
        string sub=s.substr(0,pos+1);
        return flag[pos1+1][0]=(sub1==sub);
    }
    if(pos1==-1)//边界值
    {
        string sub2=s2.substr(0,pos2+1);
        string sub=s.substr(0,pos+1);
        return flag[0][pos2+1]=(sub2==sub);
    }
    else
    {
        if( flag[pos1+1][pos2+1])//已经计算了返回计算值
            return true;        
        else
        {
            flag[pos1][pos2+1]=dp(pos1-1,pos2,pos-1);
            flag[pos1+1][pos2]=dp(pos1,pos2-1,pos-1);
            
            if( (flag[pos1][pos2+1] && s1[pos1]==s[pos]) ||
                (flag[pos1+1][pos2] && s2[pos2]==s[pos])  )
                return flag[pos1+1][pos2+1]=true;
            else
                return flag[pos1+1][pos2+1]=false;
        }    
    }
}