题目描述 Description
给出两个字符串A B，求A与B的最长公共子序列（子序列不要求是连续的）。比如两个串为：abcicba和abdkscab。ab是两个串的子序列，abc也是，abca也是，其中abca是这两个字符串最长的子序列。

输入描述 Input Description
第1行：字符串A
第2行：字符串B
(A,B的长度 <= 1000)

输出描述 Output Description
输出最长的子序列，如果有多个，输出在B中第一个出现的公共子序列

样例输入 Sample Input
abcicba
abdkscab
样例输出 Sample Output
abca

#include <iostream>
using namespace std;
string a, b;
int lena, lenb, f[1010][1010], g[1010][1010];
void dfs(int i, int j) {
    if(i==0 || j==0) return ;
    if(g[i][j] == 1) {
        dfs(i-1, j-1);
        cout << a[i];
    }else if(g[i][j] == 2) {
        dfs(i-1, j);
    }else if(g[i][j] == 3) {
        dfs(i, j-1);
    }
}
int main() {
    cin >> a >> b;
    lena = a.size();
    lenb = b.size();
    a = " " + a;
    b = " " + b;
    for(int i=1; i<=lena; i++) {
        for(int j=1; j<=lenb; j++) {
            if(a[i] == b[j]) {//左上 
                f[i][j] = f[i-1][j-1] + 1;
                g[i][j] = 1;
            }
            else if(f[i-1][j] >= f[i][j-1]) {//上方 
                f[i][j] = f[i-1][j];
                g[i][j] = 2;
            }
            else {//左方 
                f[i][j] = f[i][j-1];
                g[i][j] = 3;
            }
        }
    }
    dfs(lena, lenb); 
    return 0;
}