最长公共子序列实现

@(C Plus Plus)

最长公共子序列

前天看邹博关于最长公共子序列的问题，公式很好推导，但是实现起来没那么容易，我是用的最简单的方式，设置两个二维数组，一个用来记录子序列的长度，一个来记录方向。开始的时候把下标搞混了，结果总是不对，最后好不容易修改好了。

全部的代码如下：

#include <iostream>
#include <string>

using namespace std;

void LCS(string str1,string str2,int **c,int **b){

    int len1 = str1.size();
    int len2 = str2.size();

    for(int i=0;i<len1 +1;++i)
    {
        c[0][i] = 0;
        b[0][i] = 0;
    }
    for(int i =0;i<len2+1;++i)
    {
        c[i][0] = 0;
        b[i][0] = 0;
    }

    for(int i=1;i<len2+1;++i)
    {
        for(int j =1;j<len1+1;++j)
        {
            if(str2[i-1] == str1[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 1;
            }
            else
            {
                if(c[i-1][j] >= c[i][j-1])
                {
                    c[i][j] = c[i-1][j];
                    b[i][j] = 2;
                }
                else
                {
                    c[i][j] = c[i][j-1];
                    b[i][j] = 3;
                }
            }
        }
    }
}

void getLCS(int **c,int **b,int i,int j,string str){

    if(i == 0 || j== 0)
        return;
    if(b[i][j] == 1)
    {
        getLCS(c,b,i-1,j-1,str);
        cout<<str[i-1]<<" ";
    }
    else if(b[i][j] == 2)    {
    
        getLCS(c,b,i-1,j,str);
    }
    else
    {
        getLCS(c,b,i,j-1,str);
    }
}

int main(){

//    string str1("abcdcdab");
//    string str2("badcdcba");
    string str1("bdcaba");
    string str2("abcbdab");
    int len1 = str1.size();
    int len2 = str2.size();
    int **c = new int *[len2 + 1];
    for(int i=0;i<len2+1;++i)
        c[i] = new int [len1 +1];
    int **b = new int *[len2 +1 ];
    for(int i=0;i<len2 +1;++i)
        b[i] = new int[len1+1];

    LCS(str1,str2,c,b);
    for(int i=0;i<len2+1;++i)
    {
        for(int j =0;j<len1+1;++j)
        {
            cout<<c[i][j]<<" ";
        }
        cout<<endl;
    }

    for(int i=0;i<len2+1;++i)
    {
        for(int j =0;j<len1+1;++j)
        {
            cout<<b[i][j]<<" ";
        }
        cout<<endl;
    }

    getLCS(c,b,len2,len1,str2);
    cout<<endl;
    return 0;
}

程序有很大的局限性，另外，我没想到如何解决多解的问题。
最后求解LIS（最长递增子序列），把原序列排序后，用作保证递增的标准。然后求解两个序列的最长公共子序列，就可以求出最长递增子序列了。

现在还有的问题是：

1. 避免使用方向数组b
2. 多解问题。

参考

十分钟搞定LCS

赏

还没想好