Combine String模拟

Given three strings aa, bb and cc, your mission is to check whether cc is the combine string of aa and bb.  A string cc is said to be the combine string of aa and bb if and only if cc can be broken into two subsequences, when you read them as a string, one equals to aa, and the other equals to bb.  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 aa, bb and cc (the length of each string is between 1 and 2000).  Output For each test case, print ``Yes'', if cc is a combine string of aa and bb, otherwise print ``No''.  Sample Input abc def adebcf abc def abecdf Sample Output Yes No

Hint

题意：

给定a，b，c三个串，问c能否按序分成a和b串，不要求连续。 解题思路1： 直接模拟，1.统计处a,b,c串各个字符出现的次数，看a,b串的某个字符出现次数的和是否与c串中的相等。 2.从头往后扫描c串，看是否能按序找到a,b串。

思路2：

f[i][j]表示第一个字符串用了前i个位置（第i个位置已匹配），第二个字符串的前j个位置（第j个位置已匹配） 是否可以对c串成功匹配（成功匹配则必然会匹配到c串的前i+j个位置）。 f[i][j]==1则表示可以成功匹配 f[i][j]==0则表示无法成功匹配 显然，初始只有f[0][0]==1 所以，我们有—— f[i][j]= f[i-1][j]&&(a[i]==c[i+j]) || f[i][j-1]&&(b[j]==c[i+j]) 这样，最终f[n][m]==1则为Yes否则为No

思路1代码：

#include<stdio.h> #include<iostream> #include<string.h> #include<algorithm> #include<map> using namespace std; map<char,int>ma,mc; int main() { string a,b,c; while(cin>>a>>b>>c) { ma.clear(); mc.clear(); int lena=a.length(); int lenb=b.length(); int lenc=c.length(); for(int i=0;i<lena;i++) { ma[a[i]]++; } for(int i=0;i<lenb;i++) { ma[b[i]]++; } int x=0,y=0; for(int i=0;i<lenc;i++) { mc[c[i]]++; if(x<lena&&c[i]==a[x]) x++; if(y<lenb&&c[i]==b[y]) y++; } map<char,int>::iterator it; int flag=1; for(it=mc.begin();it!=mc.end();it++) { if(mc[it->first]!=ma[it->first]) { flag=0; break; } } if(flag) { if(x==lena&&y==lenb) { printf("Yes\n"); } else printf("No\n"); } else printf("No\n"); } }

思路2代码：

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<stack> #include<math.h> #include<vector> #include<map> #include<set> #include<cmath> #include<complex> #include<string> #include<algorithm> #include<iostream> #define exp 1e-10 #define bitnum(a) __builtin_popcount(a) using namespace std; const int N = 2005; const int M = 120; const int inf = 1600000000; const int mod = 2009; char a[N],b[N],c[N]; int dp[N][N]; int main() { int i,j,n,m,k; while(~scanf("%s",a+1)) { memset(dp,0,sizeof(dp)); scanf("%s",b+1); scanf("%s",c+1); n=strlen(a+1); m=strlen(b+1); k=strlen(c+1); if(n+m!=k) { puts("No"); continue; } dp[0][0]=1; for(i=0;i<=n;i++) for(j=0;j<=m;j++) { if(i>0&&c[i+j]==a[i]) dp[i][j]|=dp[i-1][j]; if(j>0&&c[i+j]==b[j]) dp[i][j]|=dp[i][j-1]; } /*for(i=0;i<=n;i++) { for(j=0;j<=m;j++) printf("%d ",dp[i][j]); puts(""); }*/ if(dp[n][m]) puts("Yes"); else puts("No"); } return 0; }