题目描述

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 ofabc’‘ and ``def’‘.

输入

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).

输出

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
No

题目链接：HDU-5707 https://vjudge.net/contest/432261#problem/B

题目大意：这道题目看样例比较好懂。就是判断
1.a,b为c的字串
2.a串长度+b串长度相等
3.字串顺序不能反

算法1

刚开始以为是双指针写的,可是发现双指针去写 可能有后效性 ,有时需要return ,回到上一个st1,st2的某个字母都能和c有匹配,显然双指针无法有效解决,于是网上找到了一个 双指针加LCS的题解,可能自己太菜了吧,手动抱头

(LCS+双指针)

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
int dp[4010][4010];
char a[4010],b[4010],c[4010];
int main()
{
    int l1,l2,l3,i,j;
    while(~scanf("%s",a+1))
    {
        memset(dp,0,sizeof(dp));
        scanf("%s",b+1);
        scanf("%s",c+1);
        l1=strlen(a+1);
        l2=strlen(b+1);
        l3=strlen(c+1);
        if(l1+l2!=l3)
        {
            printf("No\n");
            continue;
        }
        dp[0][0]=1;
        for(i=0;i<=l1;i++)
           for(j=0;j<=l2;j++)
           {
                if((i>0&&dp[i-1][j]&&a[i]==c[i+j])||(j>0&&dp[i][j-1]&&b[j]==c[i+j]))
                   dp[i][j]=1;
           }
        if(dp[l1][l2]!=0)
           printf("Yes\n");
        else
           printf("No\n");
    }
    return 0;
}

算法 2 DP

(LCS+双指针)

dp转移方程

//1.明确dp[i][j]的含义: dp[i][j]表示 字符串st1中有i个字母,st2中有j个字母可以与c[i+j]中前i+j个字母相匹配
//2. 用|运算符来表示是否有匹配
for(int i = 0 ; i <= len1 ; i++)
            {
                for(int j = 0 ; j <= len2 ; j++)
                {

                    if(st3[i+j] == st1[i])          
                    {
                        dp[i+1][j] |= dp[i][j];
                    }
                    if(st3[i+j] == st2[j])//
                    {
                        dp[i][j+1] |= dp[i][j];
                    }
                }
            }

C++ 代码

#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int dp[2500][2500];
int main()
{
    string st1,st2,st3;
    while(cin>>st1>>st2>>st3)
    {  memset(dp,0,sizeof(dp));
        int len1=st1.size();
        int len2=st2.size();
        int len3=st3.size();
        if(len1+len2!=len3)
        cout<<"No"<<'\n';
        else
        {  dp[0][0]=1;
            for(int i = 0 ; i <= len1 ; i++)
            {
                for(int j = 0 ; j <= len2 ; j++)
                {

                    if(st3[i+j] == st1[i])//a[i]==c[i+j]
                    {
                        dp[i+1][j] |= dp[i][j];
                    }
                    if(st3[i+j] == st2[j])//
                    {
                        dp[i][j+1] |= dp[i][j];
                    }
                }
            }
            if(dp[len1][len2]==1)
            {
                cout<<"Yes"<<'\n';
            }
            else
            cout<<"No"<<'\n';

        }
    }
}