2018/09/14最长公共子序列问题

#include <bits/stdc++.h>
using namespace std;
string a,b;
int d[100][100];
int main() {
    cin >> a >> b;
    int lena = a.length(); 
    int lenb = b.length();
    d[0][0] = a[0]==b[0] ? 1 : 0;
    for(int i=1; i<lenb; i++) d[0][i]=a[0]==b[i]?1:d[0][i-1];
    for(int i=1; i<lena; i++) d[i][0]=a[i]==b[0]?1:d[i-1][0];
    for(int i=1; i<lena; i++)
        for(int j=1; j<lenb; j++){
            if(a[i]==b[j]) d[i][j]=d[i-1][j-1]+1;
            else d[i][j]=max(d[i-1][j],d[i][j-1]);
        }
    cout << d[lena-1][lenb-1] << endl;
    int k = d[lena-1][lenb-1];
    int i=lena-1,j=lenb-1;
    char ans[k];
    while(i>-1&&j>-1){
        if(a[i]==b[j]){ans[--k] = a[i],i--,j--;}
        else if(d[i-1][j] >= d[i][j-1]) i--;
        else j--;
    }
    //puts(ans);
    for(int i=0; i<d[lena-1][lenb-1]; i++)
        putchar(ans[i]);
    return 0;
}