最长公共子序列 【微软面试100题 第五十六题】

题目要求：

　　如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串中，则字符串一称为字符串二的子串。

　　注意，并不是要求子串（字符串一）的字符必须连续出现在字符串二中。

　　请编写一个函数，输入两个字符串，求它们的最长公共子序列，并打印出最长公共序列。

　　例如：输入两个字符串BDCABA和ABCBDAB，字符串BCBA、BDAB和BCAB都是它们的最长公共子序列，则输出它们的长度4，并打印任意一个子序列。

题目分析：

　　参考链接：http://blog.csdn.net/yysdsyl/article/details/4226630

代码实现：

#include <iostream>

using namespace std;

#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN])
{
    int i, j;

    for(i = 0; i <= m; i++)
        c[i][0] = 0;
    for(j = 1; j <= n; j++)
        c[0][j] = 0;
    for(i = 1; i<= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
                b[i][j] = 0;
            }
            else if(c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
                b[i][j] = 1;
            }
            else
            {
                c[i][j] = c[i][j-1];
                b[i][j] = -1;
            }
        }
    }
}
char Store[MAXLEN] = {0};
int step = 0;
void PrintLCS(int b[][MAXLEN], char *x, int i, int j)
{
    if(i == 0 || j == 0)
        return;
    if(b[i][j] == 0)
    {
        PrintLCS(b, x, i-1, j-1);
        Store[step++] = x[i-1];
    }
    else if(b[i][j] == 1)
        PrintLCS(b, x, i-1, j);
    else
        PrintLCS(b, x, i, j-1);
}

int main(int argc, char **argv)
{
    char x[MAXLEN] = {"BDCABA"};
    char y[MAXLEN] = {"ABCBDAB"};
    int b[MAXLEN][MAXLEN];
    int c[MAXLEN][MAXLEN];
    int m, n;

    m = strlen(x);
    n = strlen(y);

    LCSLength(x, y, m, n, c, b);
    PrintLCS(b, x, m, n);
    cout << "最长公共子序列长度为：" << step << endl;
    cout << "其中一个最长公共子序列为:";
    for(int i = 0;i<step;i++)
        cout << Store[i];
    cout << endl;

    return 0;
}

扩展问题1：

　　如果要打印所有最长公共子串，怎么办？

　　参看代码实现中的pt函数，尝试遍历每一种情况，当达到最长公共子序列的长度时，就输出。

代码实现：

#include <iostream>
#include <queue>

using namespace std;
#define MAXLEN 100

void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN+1])
{
    int i, j;
   
    for(i = 0; i <= m; i++)
        c[i][0] = 0;
    for(j = 1; j <= n; j++)
        c[0][j] = 0;
    for(i = 1; i<= m; i++)
    {
        for(j = 1; j <= n; j++)
        {
            if(x[i-1] == y[j-1])
            {
                c[i][j] = c[i-1][j-1] + 1;
            }
            else if (c[i-1][j] >= c[i][j-1])
            {
                c[i][j] = c[i-1][j];
            }
            else
            {
                c[i][j] = c[i][j-1];
            }
        }
    }
}
void pt(char *x,char *y,deque< int> &que,int istart,int iend,int jstart, int jend,int lcslen)
{
     if(que.size() == lcslen)
    {
         deque< int>::iterator iter = que.begin();
          for(;iter!=que.end();iter++)
             cout << ( char)*iter << " " ;
         cout << endl;
    }
     char tmp = -1;
     for(int i = istart;i<iend;i++)
    {
         tmp = -1;
          for(int j = jstart;j<jend;j++)
         {
             
              if(x[i]==y[j] && x[i]!=tmp)
             {
                 tmp = x[i];
                 que.push_back(x[i]);
                 pt(x,y,que,i+1,iend,j+1,jend,lcslen);
                 que.pop_back();
             }
         }
    }
}
int main(int argc, char **argv)
{
    char x[MAXLEN+1] = {"BDCABA" };
    char y[MAXLEN+1] = {"ABCBDAB" };
    int c[MAXLEN+1][MAXLEN+1];
    int m, n;
   
    m = strlen(x);
    n = strlen(y);
   
    LCSLength(x, y, m, n, c);
    deque< int> que;
    pt(x,y,que,0,m,0,n,c[m][n]);
   
    return 0;
}

扩展问题2：

　　最长公共子串，这个子串要求在原字符串中是连续的。

　　我们采用一个二维矩阵来记录中间的结果。这个二维矩阵怎么构造呢？直接举个例子吧："bab"和"caba"(当然我们现在一眼就可以看出来最长公共子串是"ba"或"ab")

　　　　 b　　a　　b

　　c　　0　　0　　0

　　a　　0　　1　　0

　　b　　1　　0　　1

　　a　　0　　1　　0

　　我们看矩阵的斜对角线最长的那个就能找出最长公共子串。

　　不过在二维矩阵上找最长的由1组成的斜对角线也是件麻烦费时的事，下面改进：当要在矩阵是填1时让它等于其左上角元素加1。

　　　　 b　　a　　b

　　c　　0　　0　　0

　　a　　0　　1　　0

　　b　　1　　0　　2

　　a　　0　　2　　0

　　这样矩阵中的最大元素就是最长公共子串的长度。　

　　

#include <iostream>
#include <cstring>
using namespace std;

int LCS(const char *str1  , int len1 , const char *str2 , int len2 , char *&lcs)
{
    if(NULL == str1 || NULL == str2)
    {
        return -1;  
    }

    //    压缩后的最长子串记录向量
    int *c = new int[len2+1];
    for(int i = 0 ; i < len2 ; ++i)
    {
        c[i] = 0;
    }
    int max_len = 0;  // 匹配的长度
    int pos = 0;            //在 str2上的匹配最末位置
    for(int i = 0 ; i < len1 ; ++i)
    {
        for(int j = len2 ; j > 0 ; --j)     //更新时从后往前遍历
        {
            if(str1[i] == str2[j-1])
            {
                c[j] = c[j-1] + 1;
                if(c[j] > max_len)
                {
                    max_len = c[j];
                    pos = j-1;
                }
            }
            else
            {
                c[j] = 0;
            }
        }
    }

    if(0 == max_len)
    {
        return 0;
    }

    //    得到公共子串
    lcs = new char [max_len];
    for(int i = 0 ; i < max_len ; ++i)
    {
        lcs[i] = str2[pos-max_len+1+i];
    }
    cout<< "pos = "<<pos<<endl;
    delete [] c;
    return max_len;

}

int main()
{
    const char *str1 = "abacabad";
    const char *str2 = "cabad";
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    char *lcs;

    int len = LCS(str1 , len1 , str2 , len2 , lcs);
    cout<< "max length = "<<len<<endl;
    for(int i = 0 ; i < len ; ++i)
    {
        cout<<lcs[i]<< " ";
    }
}