LCS

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;
int LCS(const string &a, const string &b){
    int DP[a.length()+1][b.length()+1];
    memset(DP,0,sizeof(DP));
    for(int i = 1; i <= a.length(); i++)
        for(int j = 1; j <= b.length(); j++){
            if(a[i-1]==b[j-1])  DP[i][j] = DP[i-1][j-1] + 1;
            else                DP[i][j] = max(DP[i-1][j],DP[i][j-1]);
        }
    string ret = "";
    int x = b.length(), y = a.length();
    while(DP[y][x]){
        while(DP[y-1][x-1]==DP[y][x]){
            x--; y--;
        }
        while(DP[y-1][x]==DP[y][x]) y--;
        while(DP[y][x-1]==DP[y][x]) x--;
        ret += a[--y];
    }
    reverse(ret.begin(),ret.end());
    cout<<ret<<" ";
    return DP[a.length()][b.length()];
}
int main(int argc, char** argv){
    const string a = "AEKFNABGI";
    const string b = "BBSIEKQNVSW";
    cout<<LCS(a,b)<<endl;
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}