最长公共子序列“编程开发”

最长公共子序列“编程开发”

abcicba
abdkscab

abca

#include 
#include 

using namespace std;

int c[1001][1001], b[1001][1001];

void LSC(int n, int m, string x, string y)
{
    int i, j;
    for(i = 0; i <= n; i++)
        c[i][0] = 0;
    for(j = 0; j <= m; j++)
        c[0][j] = 0;
    for(i = 1; i <= n; i++)
    {
        for(j = 1; j <= m; j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i-1][j-1] = 0;
            }
            else
            {
                if(c[i-1][j] >= c[i][j-1])
                {
                    c[i][j] = c[i-1][j];
                    b[i-1][j-1] = 1;
                }
                else{
                    c[i][j] = c[i][j-1];
                    b[i-1][j-1] = -1;
                }
            }
        }
    }
}

void S_LSC(string x, int i, int j)
{
    if(i == 0 || j == 0)
        return;
    if(b[i-1][j-1] == 0)
    {
        S_LSC(x, i-1, j-1);
        cout << x[i-1];
    }
    if(b[i-1][j-1] == 1)
    {
        S_LSC(x, i-1, j);
    }
    if(b[i-1][j-1] == -1)
    {
        S_LSC(x, i, j-1);
    }
}

int main()
{
    string x, y;
    int n, m;
    cin >> x >> y;
    n = x.length();
    m = y.length();
    LSC(n, m, x, y);
    S_LSC(x, n, m);
    return 0;
}