类似LCS,构成目标单词(POJ2192)

题目链接：http://poj.org/problem?id=2192

解题报告：

1、类似最长公共子序列，dp[i][j]表示用s1前i个字符和s2前j个字符来构成目标单词的一部分，是否成功

2、状态转移方程：

if(i>&&s3[i+j-]==s1[i-]&&dp[i-][j])

    dp[i][j]=;

if(j>&&s3[i+j-]==s2[j-]&&dp[i][j-])

    dp[i][j]=;

/*#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

int main()

{

    int dp[210][210];

    char s1[210],s2[210],s3[410];

    int t,n,len1,len2,i,j;

    scanf("%d",&n);

    for(t=1; t<=n; t++)

    {

        scanf("%s%s%s",s1,s2,s3);

        len1=strlen(s1);

        len2=strlen(s2);

        memset(dp,0,sizeof(dp));

        dp[0][0]=1;

        for(i=0; i<=len1; i++)

        {

            for(j=0; j<=len2; j++)

            {

                if(i>0 && s3[i+j-1]==s1[i-1] && dp[i-1][j])

                {

                    dp[i][j]=1;

                }

                if(j>0 && s3[i+j-1]==s2[j-1] && dp[i][j-1])

                {

                    dp[i][j]=1;

                }

            }

        }

        if(dp[len1][len2])

        {

            printf("Data set %d: yes\n",t);

        }

        else

        {

            printf("Data set %d: no\n",t);

        }

    }

    return 0;

}

*/

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

int main()

{

    int Case=;

    int t;

    scanf("%d",&t);

    while(t--)

    {

        char s1[],s2[],s3[];

        scanf("%s%s%s",s1,s2,s3);

        int dp[][];///dp[i][j]表示s1前i个字符和s2前j个字符是否可以构成当前的一部分s3;

        int len1,len2;

        len1=strlen(s1);

        len2=strlen(s2);

        memset(dp,,sizeof(dp));

        dp[][]=;

        for(int i=; i<=len1; i++)

        {

            for(int j=; j<=len2; j++)

            {

                if(i>&&s3[i+j-]==s1[i-]&&dp[i-][j])

                    dp[i][j]=;

                if(j>&&s3[i+j-]==s2[j-]&&dp[i][j-])

                    dp[i][j]=;

            }

        }

        if(dp[len1][len2]==)

            printf("Data set %d: yes\n",Case++);

        else printf("Data set %d: no\n",Case++);

    }

    return ;

}