# 11579: 【原1579】LCS

### 题目描述

author: ZH 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1579 ﻿# Description 给出两个序列x[1..m]和y[1..n]，找出二者的一个最长公共子序列。一个子序列是原序列删除一些元素后得到的，剩下的元素必须保持相对顺序。例如x = ABCBDAB，y = BDCABA，则一个最长公共子序列为LCS(x, y) = BCBA。这里LCS借用函数记号来表示一个最长公共子序列。

## Sample Input

``````7 6
ABCBDAB
BDCABA
``````

## Sample Output

``````4
``````

## ligongzzz's solution

``````#include "iostream"
#include "algorithm"
#include "cstring"
using namespace std;

int ansData[1000][1000];
char str1[1009], str2[1009];
int lcs(int start1, int start2, int end1, int end2) {
if (start1 >= end1 || start2 >= end2) return 0;
//判断是否重复
if (ansData[start1][start2] >= 0) return ansData[start1][start2];
//递归
if (str1[start1] == str2[start2]) {
ansData[start1][start2] = lcs(start1 + 1, start2 + 1, end1, end2) + 1;
return ansData[start1][start2];
}
else {
ansData[start1][start2] = max(lcs(start1 + 1, start2, end1, end2),
lcs(start1, start2 + 1, end1, end2));
return ansData[start1][start2];
}
}

int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);

int len1, len2;
memset(ansData, -1, sizeof(ansData));

cin >> len1 >> len2;
cin >> str1 >> str2;

cout << lcs(0, 0, len1, len2);

return 0;
}
``````

## Neight99's solution

``````#include <cmath>
#include <iostream>

using namespace std;

const int maxN = 1e3 + 100;

int n, m, dp[maxN][maxN] = {0};
char N[maxN] = {0}, M[maxN] = {0};

int DP(int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int ans;
cin >> n >> m >> N >> M;
ans = DP(n - 1, m - 1);

cout << ans;
return 0;
}

int DP(int x, int y) {
if (x < 0 || y < 0) {
return 0;
} else if (dp[x][y] != 0) {
return dp[x][y];
} else if (N[x] == M[y]) {
dp[x][y] = DP(x - 1, y - 1) + 1;
} else {
dp[x][y] = max(DP(x - 1, y), DP(x, y - 1));
}

return dp[x][y];
}
``````

## WashSwang's solution

``````#include <iostream>
using namespace std;
int n,m,dp[1005][1005];
char x[1005],y[1005];
int main() {

cin>>n>>m;
cin>>x>>y;
for (int i=1;i<=n;++i)
for (int j=1;j<=m;++j)
{
if (x[i-1]==y[j-1])
dp[i][j]=dp[i-1][j-1]+1;
else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
cout<<dp[n][m];
return 0;
}
``````

## yyong119's solution

``````#include <iostream>
#include <algorithm>
using namespace std;
const int MAX_N = 1005;
char a[MAX_N], b[MAX_N];
int n, m;
int f[MAX_N][MAX_N];

int main() {

cin >> n >> m;
cin >> a; cin >> b;
for (int i = n; i > 0; --i) a[i] = a[i - 1];
for (int i = m; i > 0; --i) b[i] = b[i - 1];
a[0] = b[0] = '*';
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
cout << f[n][m] << endl;
return 0;
}
``````