拖拽式网站建设,企业服务总线,想开一个外企的网站怎么超做,二次元wordpress博客主题LCS
题面翻译
题目描述#xff1a;
给定一个字符串 s s s 和一个字符串 t t t #xff0c;输出 s s s 和 t t t 的最长公共子序列。
输入格式#xff1a;
两行#xff0c;第一行输入 s s s #xff0c;第二行输入 t t t 。
输出格式#xff1a;
输出 s s s…LCS
题面翻译
题目描述
给定一个字符串 s s s 和一个字符串 t t t 输出 s s s 和 t t t 的最长公共子序列。
输入格式
两行第一行输入 s s s 第二行输入 t t t 。
输出格式
输出 s s s 和 t t t 的最长公共子序列。如果有多种答案输出任何一个都可以。
说明/提示
数据保证 s s s 和 t t t 仅含英文小写字母并且 s s s 和 t t t 的长度小于等于3000。
题目描述
文字列 $ s $ および $ t $ が与えられます。 $ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ求めてください。
输入格式
入力は以下の形式で標準入力から与えられる。 $ s $ $ t $ 输出格式
$ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ出力せよ。 答えが複数ある場合、どれを出力してもよい。
样例 #1
样例输入 #1
axyb
abyxb样例输出 #1
axb样例 #2
样例输入 #2
aa
xayaz样例输出 #2
aa样例 #3
样例输入 #3
a
z样例输出 #3 样例 #4
样例输入 #4
abracadabra
avadakedavra样例输出 #4
aaadara提示
注釈
文字列 $ x $ の部分列とは、$ x $ から $ 0 $ 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。
制約
$ s $ および $ t $ は英小文字からなる文字列である。$ 1\ \leq\ |s|,\ |t|\ \leq\ 3000 $
Sample Explanation 1
答えは axb または ayb です。 どちらを出力しても正解となります。
Sample Explanation 3
答えは (空文字列) です。
#includeiostream
#includestring.h
#includealgorithm
using namespace std;
#define MAXS 3002
char arr1[MAXS], arr2[MAXS],ans[MAXS];
int dp[MAXS][MAXS],ans_num;
int main(void)
{ios::sync_with_stdio(0);cin arr1 arr2;int s1 strlen(arr1), s2 strlen(arr2);for (int i 0; i s1; i){for (int j 0; j s2; j){if (arr1[i] arr2[j]){dp[i 1][j 1] dp[i][j] 1;}else{dp[i 1][j 1] max(dp[i][j 1], dp[i 1][j]);}}}
//以上为板子int i s1-1,j s2-1 ;while(dp[i1][j1]0){while (dp[i1][j1] dp[i][j1])//i指向的arr1【i】不是公共子序列的一部分{i--;}//现在i指向了公共子序列的一部分while (j0arr1[i] ! arr2[j]){j--;}//现在i和j指向的字母相同ans[ans_num] arr1[i];ans_num;i--; j--;}for (int i ans_num - 1; i 0; i--){cout ans[i];}return 0;
}
