HDU 5707 Many Equal Substrings

清疚 2022-04-16 04:19 186阅读 0赞

## 原题目链接[HDU5707][] ##

--------------------

## 分类 ##

CodeForces KMP

--------------------

## 题意 ##

给a,b，c三个串，看c,能否由a,b构成 不能交换a, b中字符顺序， 子序列

## 思路 ##

dp\[i\]\[j\]表示c的前i+j个字符，能否由a的前i个，b的前j个构成,dp\[0\]\[0\]=1(用1表示能构成)

状态转移：当a\[i\]==c\[i+j\]时，考虑dp\[i-1\]\[j\],  
当b\[j\]=c\[i+j\]时，考虑dp\[i\]\[j-1\]

## 样例 ##

Sample Input

abc
    def
    adebcf
    abc
    def
    abecdf

Sample Output

Yes
    No

--------------------

## 代码 ##

93ms

/** * Author: GatesMa * Email: gatesma@foxmail.com * Todo: ACM Training * Date:2018/11/16 */
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 2222;
    char a[maxn], b[maxn], c[maxn];
    int dp[maxn][maxn];
    
    
    int main()
    { 
        while(cin >> a >> b >> c)
    	{ 
        	int la = strlen(a);
        	int lb = strlen(b);
        	int lc = strlen(c);
        	dp[0][0] = 1;
        	for(int i = 0; i <= la;i++){ 
        		for(int j = 0;j <= lb;j++){ 
        			if(i && j) dp[i][j] = 0;
        			if(i)
    				{ 
        				dp[i][j] = dp[i-1][j] && (a[i - 1] == c[i + j - 1]);
    				}
    				if(j)
    				{ 
    					dp[i][j] |= dp[i][j-1] && (b[j - 1] == c[i + j - 1]);
    				}
    			}
    		}
    		if(dp[la][lb] == 1 && la + lb == lc)
    		{ 
    			cout << "Yes" << endl;
    		}
    		else
    		{ 
    			cout << "No" << endl;	
    		}
    	}
        return 0;
    }

[HDU5707]: http://acm.hdu.edu.cn/showproblem.php?pid=5707

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 1238 Substring

Substrings Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Oth

阳光穿透心脏的1/2处/ 2022年09月30日 06:03/ 0 赞/ 150 阅读

相关 HDU - 1213 - How Many Tables

-------------------- 题目连接：[http://acm.hdu.edu.cn/showproblem.php?pid=1213][http_acm.hdu

梦里梦外;/ 2022年06月10日 00:09/ 0 赞/ 150 阅读

相关 HDU 1238 Substrings（暴力+stl）

You are given a number of case-sensitive strings of alphabetic characters, find the larg

刺骨的言语ヽ痛彻心扉/ 2022年06月08日 22:44/ 0 赞/ 162 阅读

相关【kmp算法】Substrings HDU - 1238

Think: 1知识点：kmp算法 2题意：T组测试数据，每组测试数据输入n个字符串，询问最长长度的子串x，要求子串x或者子串x的翻转串在每个字符串中都会出现 3思

末蓝、/ 2022年06月07日 05:10/ 0 赞/ 168 阅读

相关 HDU-How Many Tables

How Many Tables Problem Description Today is Ignatius' birthday. He invites

女爷i/ 2022年05月28日 01:10/ 0 赞/ 153 阅读

相关 KMP-Codeforces 1029A-Many Equal Substrings

KMP-Codeforces 1029A-Many Equal Substrings -------------------- 题目链接： [A. M

拼搏现实的明天。/ 2022年05月15日 07:16/ 0 赞/ 205 阅读

相关 CodeForces - 1029A Many Equal Substrings

原题目链接[CodeForces - 1029A][] -------------------- 分类 CodeForces KMP -------------

喜欢ヅ旅行/ 2022年04月16日 04:20/ 0 赞/ 184 阅读

相关 HDU 5707 Many Equal Substrings

原题目链接[HDU5707][] -------------------- 分类 CodeForces KMP -------------------- 题

清疚/ 2022年04月16日 04:19/ 0 赞/ 187 阅读

相关 HDU-1213-How Many Tables

链接：https://vjudge.net/problem/HDU-1213 题意：给n个人m个连通，求有几组思路：并查集模板代码：

女爷i/ 2021年12月24日 05:05/ 0 赞/ 216 阅读

相关 hdu 三部曲 Get Many Persimmon Trees

Problem Description Seiji Hayashi had been a professor of the Nisshinkan Samurai School

àì夳堔傛蜴生んèń/ 2021年12月23日 19:13/ 0 赞/ 224 阅读