注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

微软、Google等面试题

剑指Offer:名企面试官精讲典型编程题

 
 
 

日志

 
 

程序员面试题精选100题(20)-最长公共子串[算法]  

2007-04-07 18:43:01|  分类: 动态规划 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。

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

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

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

先介绍LCS问题的性质:记Xm={x0, x1,…xm-1}Yn={y0,y1,…,yn-1}为两个字符串,而Zk={z0,z1,…zk-1}是它们的LCS,则:

1.       如果xm-1=yn-1,那么zk-1=xm-1=yn-1,并且Zk-1Xm-1Yn-1LCS
2.       如果xm-1≠yn-1,那么当zk-1≠xm-1ZXm-1YLCS
3.       如果xm-1≠yn-1,那么当zk-1≠yn-1ZYn-1XLCS

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

1.       如果zk-1≠xm-1,那么我们可以把xm-1yn-1)加到Z中得到Z’,这样就得到XY的一个长度为k+1的公共子串Z’。这就与长度为kZXYLCS相矛盾了。因此一定有zk-1=xm-1=yn-1

既然zk-1=xm-1=yn-1,那如果我们删除zk-1xm-1yn-1)得到的Zk-1Xm-1Yn-1,显然Zk-1Xm-1Yn-1的一个公共子串,现在我们证明Zk-1Xm-1Yn-1LCS。用反证法不难证明。假设有Xm-1Yn-1有一个长度超过k-1的公共子串W,那么我们把加到W中得到W’,那W’就是XY的公共子串,并且长度超过k,这就和已知条件相矛盾了。

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

3.       证明同2

有了上面的性质,我们可以得出如下的思路:求两字符串Xm={x0, x1,…xm-1}Yn={y0,y1,…,yn-1}LCS,如果xm-1=yn-1,那么只需求得Xm-1Yn-1LCS,并在其后添加xm-1yn-1)即可;如果xm-1≠yn-1,我们分别求得Xm-1YLCSYn-1XLCS,并且这两个LCS中较长的一个为XYLCS

如果我们记字符串XiYjLCS的长度为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 xi=x
j
         \       max(c[i,j-1],c[i-1,j]           if i,j>=0 and xi≠xj

上面的公式用递归函数不难求得。但从前面求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);
      }
}

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

博主何海涛对本博客文章享有版权。网络转载请注明出处http://zhedahht.blog.163.com/。整理出版物请和作者联系。对解题思路有任何建议,欢迎在评论中告知,或者加我微博http://weibo.com/zhedahht或者http://t.163.com/zhedahht与我讨论。谢谢。

  评论这张
 
阅读(29780)| 评论(35)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017