hdu5707-Combine String（DP）

Problem Description

Given three strings a, b and c , your mission is to check whether c is the combine string of a and b .
A string c is said to be the combine string of a and b if and only if c can be broken into two subsequences, when you read them as a string, one equals to a , and the other equals to b .
For example, ``adebcf'' is a combine string of ``abc'' and ``def''.

Input

Input file contains several test cases (no more than 20). Process to the end of file.
Each test case contains three strings a, b and c (the length of each string is between 1 and 2000).

Output

For each test case, print ``Yes'', if c is a combine string of a and b , otherwise print ``No''.

Sample Input

abc

def

adebcf

abc

def

abecdf

Sample Output

Yes

思路：dp[i][j]表示第一个字符串用了前i个位置（第i个位置已匹配），第二个字符串的前j个位置（第j个位置已匹配）
是否可以对c串成功匹配（成功匹配则必然会匹配到c串的前i+j个位置）。
dp[i][j]==1则表示可以成功匹配
dp[i][j]==0则表示无法成功匹配

代码：

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

const int maxn=;

int dp[maxn][maxn];

int main()

{

    string a,b,c;

    while(cin>>a>>b>>c){

        memset(dp,,sizeof(dp));

        if(c.size()!=a.size()+b.size())

            printf("No\n");

        else{

            dp[][]=;

            for(int i=;i<=a.size();i++){

                for(int j=;j<=b.size();j++){

                    if(a[i]==c[i+j]){

                        dp[i+][j]|=dp[i][j];

                    }

                    if(b[j]==c[i+j]){

                        dp[i][j+]|=dp[i][j];

                    }

                }

            }

            if(dp[a.size()][b.size()]==){

                printf("Yes\n");

            }else{

                printf("No\n");

            }

        }

    }

    return ;

}

巴特西

hdu5707-Combine String（DP）

最新文章

热门文章