最长公共子串

【转】http://zhedahht.blog.163.com/blog/static/254111742007376431815/

 

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

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

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，因此一些重视算法的公司像MicroStrategy都把它当作面试题。

完整介绍动态规划将需要很长的篇幅，因此我不打算在此全面讨论动态规划相关的概念，只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉，请参考相关算法书比如算法讨论。

先介绍LCS问题的性质：记X_m={x₀, x₁,…x_m-1}和Y_n={y₀,y₁,…,y_n-1}为两个字符串，而Z_k={z₀,z₁,…z_k-1}是它们的LCS，则：

1.       如果x_m-1=y_n-1，那么z_k-1=x_m-1=y_n-1，并且Z_k-1是X_m-1和Y_n-1的LCS；
2.       如果x_m-1≠y_n-1，那么当z_k-1≠x_m-1时Z是X_m-1和Y的LCS；
3.       如果x_m-1≠y_n-1，那么当z_k-1≠y_n-1时Z是Y_n-1和X的LCS；

下面简单证明一下这些性质：

1.       如果z_k-1≠x_m-1，那么我们可以把x_m-1（y_n-1）加到Z中得到Z’，这样就得到X和Y的一个长度为k+1的公共子串Z’。这就与长度为k的Z是X和Y的LCS相矛盾了。因此一定有z_k-1=x_m-1=y_n-1。

既然z_k-1=x_m-1=y_n-1，那如果我们删除z_k-1（x_m-1、y_n-1）得到的Z_k-1，X_m-1和Y_n-1，显然Z_k-1是X_m-1和Y_n-1的一个公共子串，现在我们证明Z_k-1是X_m-1和Y_n-1的LCS。用反证法不难证明。假设有X_m-1和Y_n-1有一个长度超过k-1的公共子串W，那么我们把加到W中得到W’，那W’就是X和Y的公共子串，并且长度超过k，这就和已知条件相矛盾了。

2.       还是用反证法证明。假设Z不是X_m-1和Y的LCS，则存在一个长度超过k的W是X_m-1和Y的LCS，那W肯定也X和Y的公共子串，而已知条件中X和Y的公共子串的最大长度为k。矛盾。

3.       证明同2。

有了上面的性质，我们可以得出如下的思路：求两字符串X_m={x₀, x₁,…x_m-1}和Y_n={y₀,y₁,…,y_n-1}的LCS，如果x_m-1=y_n-1，那么只需求得X_m-1和Y_n-1的LCS，并在其后添加x_m-1（y_n-1）即可；如果x_m-1≠y_n-1，我们分别求得X_m-1和Y的LCS和Y_n-1和X的LCS，并且这两个LCS中较长的一个为X和Y的LCS。

如果我们记字符串X_i和Y_j的LCS的长度为c[i,j]，我们可以递归地求c[i,j]：

          /      0                               if i<0 or j<0
c[i,j]=          c[i-1,j-1]+1                    if i,j>=0 and x_i=x_j
         \       max(c[i,j-1],c[i-1,j]           if i,j>=0 and x_i≠x_j

上面的公式用递归函数不难求得。但从前面求Fibonacci第n项(本面试题系列第16题）的分析中我们知道直接递归会有很多重复计算，我们用从底向上循环求解的思路效率更高。

为了能够采用循环求解的思路，我们用一个矩阵（参考代码中的LCS_length）保存下来当前已经计算好了的c[i,j]，当后面的计算需要这些数据时就可以直接从矩阵读取。另外，求取c[i,j]可以从c[i-1,j-1] 、c[i,j-1]或者c[i-1,j]三个方向计算得到，相当于在矩阵LCS_length中是从c[i-1,j-1]，c[i,j-1]或者c[i-1,j]的某一个各自移动到c[i,j]，因此在矩阵中有三种不同的移动方向：向左、向上和向左上方，其中只有向左上方移动时才表明找到LCS中的一个字符。于是我们需要用另外一个矩阵（参考代码中的LCS_direction）保存移动的方向。

参考代码如下：

#include "string.h"

// directions of LCS generation
enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp};

/////////////////////////////////////////////////////////////////////////////
// Get the length of two strings' LCSs, and print one of the LCSs
// Input: pStr1         - the first string
//        pStr2         - the second string
// Output: the length of two strings' LCSs
/////////////////////////////////////////////////////////////////////////////
int LCS(char* pStr1, char* pStr2)
{
      if(!pStr1 || !pStr2)
            return 0;

      size_t length1 = strlen(pStr1);
      size_t length2 = strlen(pStr2);
      if(!length1 || !length2)
            return 0;

      size_t i, j;

      // initiate the length matrix
      int **LCS_length;
      LCS_length = (int**)(new int[length1]);
      for(i = 0; i < length1; ++ i)
            LCS_length[i] = (int*)new int[length2];

      for(i = 0; i < length1; ++ i)
            for(j = 0; j < length2; ++ j)
                  LCS_length[i][j] = 0;

 

      // initiate the direction matrix
      int **LCS_direction;
      LCS_direction = (int**)(new int[length1]);
      for( i = 0; i < length1; ++ i)
            LCS_direction[i] = (int*)new int[length2];

      for(i = 0; i < length1; ++ i)
            for(j = 0; j < length2; ++ j)
                  LCS_direction[i][j] = kInit;

      for(i = 0; i < length1; ++ i)
      {
            for(j = 0; j < length2; ++ j)
            {
                  if(i == 0 || j == 0)
                  {
                        if(pStr1[i] == pStr2[j])
                        {
                              LCS_length[i][j] = 1;
                              LCS_direction[i][j] = kLeftUp;
                        }
                        else
                              LCS_length[i][j] = 0;
                  }
                  // a char of LCS is found, 
                  // it comes from the left up entry in the direction matrix
                  else if(pStr1[i] == pStr2[j])
                  {
                        LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1;
                        LCS_direction[i][j] = kLeftUp;
                  }
                  // it comes from the up entry in the direction matrix
                  else if(LCS_length[i - 1][j] > LCS_length[i][j - 1])
                  {
                        LCS_length[i][j] = LCS_length[i - 1][j];
                        LCS_direction[i][j] = kUp;
                  }
                  // it comes from the left entry in the direction matrix
                  else
                  {
                        LCS_length[i][j] = LCS_length[i][j - 1];
                        LCS_direction[i][j] = kLeft;
                  }
            }
      }
      LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1);

      return LCS_length[length1 - 1][length2 - 1];
}

 

/////////////////////////////////////////////////////////////////////////////
// Print a LCS for two strings
// Input: LCS_direction - a 2d matrix which records the direction of
//                        LCS generation
//        pStr1         - the first string
//        pStr2         - the second string
//        row           - the row index in the matrix LCS_direction
//        col           - the column index in the matrix LCS_direction
/////////////////////////////////////////////////////////////////////////////
void LCS_Print(int **LCS_direction, 
                    char* pStr1, char* pStr2, 
                    size_t row, size_t col)
{
      if(pStr1 == NULL || pStr2 == NULL)
            return;

      size_t length1 = strlen(pStr1);
      size_t length2 = strlen(pStr2);

      if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2))
            return;

      // kLeftUp implies a char in the LCS is found
      if(LCS_direction[row][col] == kLeftUp)
      {
            if(row > 0 && col > 0)
                  LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1);

            // print the char
            printf("%c", pStr1[row]);
      }
      else if(LCS_direction[row][col] == kLeft)
      {
            // move to the left entry in the direction matrix
            if(col > 0)
                  LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1);
      }
      else if(LCS_direction[row][col] == kUp)
      {
            // move to the up entry in the direction matrix
            if(row > 0)
                  LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col);
      }
}

扩展：如果题目改成求两个字符串的最长公共子字符串，应该怎么求？子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。