F - LCS
Time Limit: 2 sec / Memory Limit: 1024 MB
Score : 100100 points
Problem Statement
You are given strings ss and tt. Find one longest string that is a subsequence of both ss and tt.
Notes
A subsequence of a string xx is the string obtained by removing zero or more characters from xx and concatenating the remaining characters without changing the order.
Constraints
- ss and tt are strings consisting of lowercase English letters.
- 1≤|s|,|t|≤30001≤|s|,|t|≤3000
Input
Input is given from Standard Input in the following format:
ss
tt
Output
Print one longest string that is a subsequence of both ss and tt. If there are multiple such strings, any of them will be accepted.
Sample Input 1 Copy
Copy
axyb
abyxb
Sample Output 1 Copy
Copy
axb
The answer is axb or ayb; either will be accepted.
Sample Input 2 Copy
Copy
aa
xayaz
Sample Output 2 Copy
Copy
aa
Sample Input 3 Copy
Copy
a
z
Sample Output 3 Copy
Copy
The answer is (an empty string).
Sample Input 4 Copy
Copy
abracadabra
avadakedavra
Sample Output 4 Copy
Copy
aaadara 题意：给定两个字符串s和t，让你求出这两个字符串的最长公共子序列，并输出最长公共子序列。
思路：先通过DP求出LCS的DP信息，然后再根据DP信息输出对应的字符。
裸题主要看思路。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
const int maxn=;
const int inf=0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
int dp[][];
char a[maxn];
char b[maxn];
int n,m;
int c[maxn];
int pre[maxn];
int lis[maxn];
int main()
{
scanf("%s",a);
scanf("%s",b);
n=strlen(a);
m=strlen(b);
for(int i=n-;i>=;i--)
{
for(int j=m-;j>=;j--)
{
if(a[i]==b[j])
{
dp[i][j]=dp[i+][j+]+;
}else
{
dp[i][j]=max(dp[i+][j],dp[i][j+]);
}
}
}
// cout<<dp[n-1][m-1]<<endl;
int i=;
int j=;
while(i<n&&j<m)
{
if(a[i]==b[j])
{
putchar(a[i]);
i++;
j++;
}else if(dp[i][j]==dp[i+][j])
{
i++;
}else
{
j++;
}
} return ;
} inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * - ch + '';
}
}
else {
*p = ch - '';
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}