LCS

题面翻译

题目描述：

给定一个字符串 $s$ 和一个字符串 $t$ ，输出 $s$ 和 $t$ 的最长公共子序列。

输入格式：

两行，第一行输入 $s$ ，第二行输入 $t$ 。

输出格式：

输出 $s$ 和 $t$ 的最长公共子序列。如果有多种答案，输出任何一个都可以。

说明/提示：

数据保证 $s$ 和 $t$ 仅含英文小写字母，并且 $s$ 和 $t$ 的长度小于等于3000。

题目描述

文字列 $ s $ および $ t $ が与えられます。 $ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$ s $ $ t $

输出格式

$ s $ の部分列かつ $ t $ の部分列であるような文字列のうち、最長のものをひとつ出力せよ。 答えが複数ある場合、どれを出力してもよい。

样例 #1

样例输入 #1

1
2
axyb
abyxb

样例输出 #1

1
axb

样例 #2

样例输入 #2

1
2
aa
xayaz

样例输出 #2

1
aa

样例 #3

样例输入 #3

1
2
a
z

样例输出 #3

1

样例 #4

样例输入 #4

1
2
abracadabra
avadakedavra

样例输出 #4

1
aaadara

提示

注釈

文字列 $ x $ の部分列とは、$ x $ から $ 0 $ 個以上の文字を取り除いた後、残りの文字を元の順序で連結して得られる文字列のことです。

制約

  • $ s $ および $ t $ は英小文字からなる文字列である。
  • $ 1\ \leq\ |s|,\ |t|\ \leq\ 3000 $

Sample Explanation 1

答えは axb または ayb です。 どちらを出力しても正解となります。

Sample Explanation 3

答えは `` (空文字列) です。

题解

题目解析

一道LCS题,LCS最长个数是经典DP问题,不用我多说了.这一次需要把最长的LCS输出,也相当于一个模板吧.但是这个功能的写法我RE了八次,整整八次……

简单解释一下,dp数组中存储的信息其实已经蕴含了LCS的构造信息了,我们需要的是利用dp数组中的信息反推出我们LCS是怎么构造的.

具体方法是:

  • 首先定义两个指针,都初始化为它们各自的尾部位置.
  • 如果两个指针的位置所在的字符相同,则把这个字符加到答案串里.
  • 如果两个指针所在位置的字符不相同,则分为两个情况:
    • 如果 dp[i][j] == dp[i][j-1] 也就是说j位置和j-1位置是等价的,我们就把j所在指针往前移动.
    • 如果 dp[i][j] == dp[i-1][j] 也就是说i位置和i-1位置是等价的,我们就把i所在指针往前移动.

最后答案串就是我们的输出结果,注意我们是从后往前遍历,所以答案串要从后往前加.

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define CIN_ ios::sync_with_stdio(0)
#define CIN cin.tie(0)
#define MAXN(size) const long long MAXN = size + 100
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
#define T_ int T;cin >> T;while(T--)
typedef long long ll;
typedef unsigned long long ull;

MAXN(1e4);
int dp[MAXN][MAXN];

signed main(){
    string s1,s2;
    cin >> s1 >> s2;
    s1 = " " + s1;//为了防止出现负数情况dp[0][0]=dp[-1][0]那种
    s2 = " " + s2;
    if(s1[0] == s2[0]) dp[0][0] = 1;
    fa(1,s1.size()-1,1){
    	for(int j=1;j<s2.size();j++){
    		if(s1[i] == s2[j]){
    			dp[i][j] = dp[i-1][j-1] + 1;
    		}else{
    			dp[i][j] = max(dp[i-1][j] , dp[i][j-1]);
    		}
    	}
    }
    string ans = "";
    int t1 = s1.size()-1,t2 = s2.size()-1;
    while(t1 >= 1 && t2 >= 1){//这里一定要用指针的位置作为while条件,我就是因为没用这个RE了八发.
    	if(s1[t1] == s2[t2]){
    		if(s1[t1] != ' ') ans = s1[t1] + ans;
    		t1--,t2--;
    	}else{
    		if(dp[t1][t2] == dp[t1-1][t2]){
    			t1--;
    		}else{
    			t2--;
    		}
    	}
    }
    cout << ans;
    return 0;
}