深入解析最长公共子串

题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。
例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,则输出它们的长度4,并打印任意一个子串。
分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。
完整介绍动态规划将需要很长的篇幅,因此我不打算在此全面讨论动态规划相关的概念,只集中对LCS直接相关内容作讨论。如果对动态规划不是很熟悉,请参考相关算法书比如算法讨论。
考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bn-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:
(1) 如果am-1==bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;
(2) 如果am-1!=bn-1,则若zk-1!=am-1时,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;
(3) 如果am-1!=bn-1,则若zk-1!=bn-1时,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。
      这样,在找A和B的公共子序列时,如果有am-1==bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。
求解:
引进一个二维数组c[][],用c[i][j]记录X[i]与Y[j] 的LCS 的长度,b[i][j]记录c[i][j]是通过哪一个子问题的值求得的,以决定输出最长公共字串时搜索的方向。
我们是自底向上进行递推计算,那么在计算c[i,j]之前,c[i-1][j-1],c[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i] == Y[j]还是X[i] != Y[j],就可以计算出c[i][j]。
问题的递归式写成:  

      回溯输出最长公共子序列过程:

 

算法分析:
由于每次调用至少向上或向左(或向上向左同时)移动一步,故最多调用(m + n)次就会遇到i = 0或j = 0的情况,此时开始返回。返回时与递归调用时方向相反,步数相同,故算法时间复杂度为Θ(m + n)。
完整的实现代码如下:


代码如下:

/**
找出两个字符串的最长公共子串的长度
** author :liuzhiwei 
** data   :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2, int **b)
{
 int i,j,length1,length2,len;
 length1 = strlen(str1);
 length2 = strlen(str2);
 //双指针的方法申请动态二维数组
 int **c = new int*[length1+1];      //共有length1+1行
 for(i = 0; i < length1+1; i++)
  c[i] = new int[length2+1];      //共有length2+1列
 for(i = 0; i < length1+1; i++)
  c[i][0]=0;        //第0列都初始化为0
 for(j = 0; j < length2+1; j++)
  c[0][j]=0;        //第0行都初始化为0
 for(i = 1; i < length1+1; i++)
 {
  for(j = 1; j < length2+1; j++)
  {
   if(str1[i-1]==str2[j-1])   //由于c[][]的0行0列没有使用,c[][]的第i行元素对应str1的第i-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;
   }
  }
 }
 /*
 for(i= 0; i < length1+1; i++)
 {
 for(j = 0; j < length2+1; j++)
 printf("%d ",c[i][j]);
 printf("\n");
 }
 */
 len=c[length1][length2];
 for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
  delete[] c[i];
 delete[] c;
 return len;
}
void PrintLCS(int **b, char *str1, int i, int j)
{
 if(i==0 || j==0)
  return ;
 if(b[i][j]==0)
 {
  PrintLCS(b, str1, i-1, j-1);   //从后面开始递归,所以要先递归到子串的前面,然后从前往后开始输出子串
  printf("%c",str1[i-1]);        //c[][]的第i行元素对应str1的第i-1个元素
 }
 else if(b[i][j]==1)
  PrintLCS(b, str1, i-1, j);
 else
  PrintLCS(b, str1, i, j-1);
}
int main(void)
{
 char str1[100],str2[100];
 int i,length1,length2,len;
 printf("请输入第一个字符串:");
 gets(str1);
 printf("请输入第二个字符串:");
 gets(str2);
 length1 = strlen(str1);
 length2 = strlen(str2);
 //双指针的方法申请动态二维数组
 int **b = new int*[length1+1];
 for(i= 0; i < length1+1; i++)
  b[i] = new int[length2+1];
 len=LCSLength(str1,str2,b);
 printf("最长公共子串的长度为:%d\n",len);
 printf("最长公共子串为:");
 PrintLCS(b,str1,length1,length2);
 printf("\n");
 for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
  delete[] b[i];
 delete[] b;
 system("pause");
 return 0;
}

程序的效果图如下:

第二种方法为:


代码如下:

/**
找出两个字符串的最长公共子串的长度
** author :liuzhiwei 
** data   :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int LCSLength(char* str1, char* str2)    //求得两个字符串的最大公共子串长度并输出公共子串
{
 int i,j,length1,length2;
 length1 = strlen(str1);
 length2 = strlen(str2);
 //双指针的方法申请动态二维数组
 int **c = new int*[length1+1];      //共有length1+1行
 for(i = 0; i < length1+1; i++)
  c[i] = new int[length2+1];      //共有length2+1列
 for(i = 0; i < length1+1; i++)
  c[i][0]=0;        //第0列都初始化为0
 for(j = 0; j < length2+1; j++)
  c[0][j]=0;        //第0行都初始化为0
 for(i = 1; i < length1+1; i++)
 {
  for(j = 1; j < length2+1; j++)
  {
   if(str1[i-1]==str2[j-1])   //由于c[][]的0行0列没有使用,c[][]的第i行元素对应str1的第i-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];
  }
 }
 //输出公共子串
 char s[100];
 int len,k;
 len=k=c[length1][length2];
 s[k--]='\0';
 i=length1,j=length2;
 while(i>0 && j>0)
 {
  if(str1[i-1]==str2[j-1])
  {
   s[k--]=str1[i-1];
   i--;
   j--;
  }
  else if(c[i-1][j]<c[i][j-1])
   j--;
  else
   i--;
 }
 printf("最长公共子串为:");
 puts(s);
 for(i = 0; i < length1+1; i++)    //释放动态申请的二维数组
  delete[] c[i];
 delete[] c;
 return len;
}
int main(void)
{
 char str1[100],str2[100];
 int length1,length2,len;
 printf("请输入第一个字符串:");
 gets(str1);
 printf("请输入第二个字符串:");
 gets(str2);
 length1 = strlen(str1);
 length2 = strlen(str2);
 len=LCSLength(str1,str2);
 printf("最长公共子串的长度为:%d\n",len);
 system("pause");
 return 0;
}

问题拓展:设A、B、C是三个长为n的字符串,它们取自同一常数大小的字母表。设计一个找出三个串的最长公共子串的O(n^3)的时间算法。
思路:跟上面的求2个字符串的公共子串是一样的思路,只不过这里需要动态申请一个三维的数组,三个字符串的尾字符不同的时候,考虑的情况多一些而已。


代码如下:

/**
找出三个字符串的最长公共子串的长度
** author :liuzhiwei 
** data   :2011-08-15
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int max1(int m,int n)
{
 if(m>n)
  return m;
 else
  return n;
}
int max2(int x,int y,int z,int k,int m,int n)
{
 int max=-1;
 if(x>max)
  max=x;
 if(y>max)
  max=y;
 if(z>max)
  max=z;
 if(k>max)
  max=k;
 if(m>max)
  max=m;
 if(n>max)
  max=n;
 return max;
}
int LCSLength(char* str1, char* str2, char* str3)    //求得三个字符串的最大公共子串长度并输出公共子串
{
 int i,j,k,length1,length2,length3,len;
 length1 = strlen(str1);
 length2 = strlen(str2);
 length3 = strlen(str3);
 //申请动态三维数组
 int ***c = new int**[length1+1];      //共有length1+1行
 for(i = 0; i < length1+1; i++)
 {
  c[i] = new int*[length2+1];      //共有length2+1列
  for(j = 0; j<length2+1; j++)
   c[i][j] = new int[length3+1];
 }
 for(i = 0; i < length1+1; i++)
 {
  for(j = 0; j < length2+1; j++)
   c[i][j][0]=0;
 }
 for(i = 0; i < length2+1; i++)
 {
  for(j = 0; j < length3+1; j++)
   c[0][i][j]=0;
 }
 for(i = 0; i < length1+1; i++)
 {
  for(j = 0; j < length3+1; j++)
   c[i][0][j]=0;  
 }
 for(i = 1; i < length1+1; i++)
 {
  for(j = 1; j < length2+1; j++)
  {
   for(k = 1; k < length3+1; k++)
   {
    if(str1[i-1]==str2[j-1] && str2[j-1]==str3[k-1])
     c[i][j][k]=c[i-1][j-1][k-1]+1;
    else if(str1[i-1]==str2[j-1] && str1[i-1]!=str3[k-1])
     c[i][j][k]=max1(c[i][j][k-1],c[i-1][j-1][k]);
    else if(str1[i-1]==str3[k-1] && str1[i-1]!=str2[j-1])
     c[i][j][k]=max1(c[i][j-1][k],c[i-1][j][k-1]);
    else if(str2[j-1]==str3[k-1] && str1[i-1]!=str2[j-1])
     c[i][j][k]=max1(c[i-1][j][k],c[i][j-1][k-1]);
    else
    {
     c[i][j][k]=max2(c[i-1][j][k],c[i][j-1][k],c[i][j][k-1],c[i-1][j-1][k],c[i-1][j][k-1],c[i][j-1][k-1]);
    }
   }
  }
 }
 len=c[length1][length2][length3];
 for(i = 1; i < length1+1; i++)          //释放动态申请的三维数组
 {
  for(j = 1; j < length2+1; j++)
   delete[] c[i][j];
  delete[] c[i];
 }
 delete[] c;
 return len;
}
int main(void)
{
 char str1[100],str2[100],str3[100];
 int len;
 printf("请输入第一个字符串:");
 gets(str1);
 printf("请输入第二个字符串:");
 gets(str2);
 printf("请输入第三个字符串:");
 gets(str3);
 len=LCSLength(str1,str2,str3);
 printf("最长公共子串的长度为:%d\n",len);
 system("pause");
 return 0;
}

程序的效果图如下:

时间: 2013-05-20

C++实现寻找最低公共父节点的方法

本文实例讲述了C++实现寻找最低公共父节点的方法,是数据结构中二叉树的经典算法.分享给大家供大家参考.具体方法如下: 最低公共父节点,意思很好理解. 思路1:最低公共父节点满足这样的条件:两个节点分别位于其左子树和右子树,那么定义两个bool变量,leftFlag和rightFlag,如果在左子树中,leftFlag为true,如果在右子树中,rightFlag为true,仅当leftFlag == rightFlag == true时,才能满足条件. 实现代码如下: #include <ios

java实现字符串匹配求两个字符串的最大公共子串

本文实例讲述了java实现求两个字符串最大公共子串的方法.分享给大家供大家参考,具体如下: 最近在项目工作中有一个关于文本对比的需求,经过这段时间的学习,总结了这篇博客内容:求两个字符串的最大公共子串. 算法思想:基于图计算两字符串的公共子串.具体算法思想参照下图: 输入字符串S1:achmacmh    输入字符串S2:macham 第a步,是将字符串s1,s2分别按字节拆分,构成一个二维数组: 二维数组中的值如b所示,比如第一行第一列的值表示字符串s2和s1的第一个字节是否相等,若相等就是1

Python最长公共子串算法实例

本文实例讲述了Python最长公共子串算法.分享给大家供大家参考.具体如下: #!/usr/bin/env python # find an LCS (Longest Common Subsequence). # *public domain* def find_lcs_len(s1, s2): m = [ [ 0 for x in s2 ] for y in s1 ] for p1 in range(len(s1)): for p2 in range(len(s2)): if s1[p1] =

JavaScript自定义函数实现查找两个字符串最长公共子串的方法

本文实例讲述了JavaScript自定义函数实现查找两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: //查找两个字符串的最长公共子串 function findSubStr(s1,s2){ var S=sstr= "" ,L1=s1.length,L2=s2.length; if (L1>L2){ var s3=s1;s1=s2,s2=s3,L1=s2.length;} for ( var j=L1;j> 0 ;j--) for ( var i= 0 ;i&

C语言求两个字符串的最长公共子串

本文实例讲述了C语言求两个字符串的最长公共子串的方法.分享给大家供大家参考.具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * str3); int stringLength(char * str); void main(){ char str1[50]; char st

利用C++实现最长公共子序列与最长公共子串

一.问题描述 子串应该比较好理解,至于什么是子序列,这里给出一个例子:有两个母串 cnblogs belong 比如序列bo, bg, lg在母串cnblogs与belong中都出现过并且出现顺序与母串保持一致,我们将其称为公共子序列.最长公共子序列(Longest Common Subsequence, LCS),顾名思义,是指在所有的子序列中最长的那一个.子串是要求更严格的一种子序列,要求在母串中连续地出现.在上述例子的中,最长公共子序列为blog(cnblogs, belong),最长公共

java实现求两个字符串最长公共子串的方法

本文实例讲述了java实现求两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: 这个是华为OJ上的一道题目.首先,如果我们用java写代码,华为OJ有以下三条规则需遵守,否则编译无法通过或者用例无法通过,规则如下: (1)一定不可以有包名: (2)主类名只能为Main: (3)不可以输出与结果无关的信息. 好了,按照以上规则,我们写出来的代码如下(此代码不是最优的,只是用来记录华为OJ上java代码的书写规则): import java.util.Scanner; public cl

Ruby实现的最长公共子序列算法

最长公共子序列,LCS,动态规划实现. #encoding: utf-8 #author: xu jin, 4100213 #date: Nov 01, 2012 #Longest-Commom-Subsequence #to find a longest commom subsequence of two given character arrays by using LCS algorithm #example output: #The random character arrays are

Java算法之最长公共子序列问题(LCS)实例分析

本文实例讲述了Java算法之最长公共子序列问题(LCS).分享给大家供大家参考,具体如下: 问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X= { x1, x2,-, xm},则另一序列Z= {z1, z2,-, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,-, ik},使得对于所有j=1,2,-,k有 Xij=Zj.例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,

Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法

本文实例讲述了Python使用回溯法子集树模板获取最长公共子序列(LCS)的方法.分享给大家供大家参考,具体如下: 问题 输入 第1行:字符串A 第2行:字符串B (A,B的长度 <= 1000) 输出 输出最长的子序列,如果有多个,随意输出1个. 输入示例 belong cnblogs 输出示例 blog 分析 既然打算套用回溯法子集树模板,那就要祭出元素-状态空间分析大法. 以长度较小的字符串中的字符作为元素,以长度较大的字符串中的字符作为状态空间,对每一个元素,遍历它的状态空间,其它的事情

javascript实现最长公共子序列实例代码

介绍 最长公共子序列(Longest Common Subsequence LCS)是从给定的两个序列X和Y中取出尽可能多的一部分字符,按照它们在原序列排列的先后次序排列得到.LCS问题的算法用途广泛,如在软件不同版本的管理中,用LCS算法找到新旧版本的异同处;在软件测试中,用LCS算法对录制和回放的序列进行比较,在基因工程领域,用LCS算法检查患者DNA连与键康DNA链的异同;在防抄袭系统中,用LCS算法检查论文的抄袭率.LCS算法也可以用于程序代码相似度度量,人体运行的序列检索,视频段匹配等

Java基于动态规划法实现求最长公共子序列及最长公共子字符串示例

本文实例讲述了Java基于动态规划法实现求最长公共子序列及最长公共子字符串.分享给大家供大家参考,具体如下: 动态规划法 经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题.简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加. 为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法. [问题] 求两字符序列的最长公共字符子序列 问题描述:字符

Python求两个字符串最长公共子序列代码实例

一.问题描述 给定两个字符串,求解这两个字符串的最长公共子序列(Longest Common Sequence).比如字符串1:BDCABA:字符串2:ABCBDAB.则这两个字符串的最长公共子序列长度为4,最长公共子序列是:BCBA 二.算法求解 这是一个动态规划的题目.对于可用动态规划求解的问题,一般有两个特征:①最优子结构:②重叠子问题 ①最优子结构 设X=(x1,x2,...,xn)和Y=(y1,y2,...,ym)是两个序列,将X和Y的最长公共子序列记为LCS(X,Y) 找出LCS(X

Java最长公共子序列示例源码

最长公共子序列(Longest Common Subsequence)定义:两个或多个已知数列的子序列集合中最长的就是最长公共子序列.其实说到最长公共子序列,还有一个要提到的是最长公共子串(Longest Common Substring),它指的是两个字符串中的最长公共子串,要求子串一定连续.关于最长公共子串的内容我们后续也会讲到,今天先来看下最长公共子序列的相关内容. 之前看过一个LCS算法的实现过程,觉得太过繁琐.自己写了一个比较简单的,此处仅仅介绍实现过程. 程序代码测试通过,需要的童鞋

详解Python最长公共子串和最长公共子序列的实现

最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题.解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0.然后求出对角线最长的1的序列,其对应的位置就是最长匹配子串的位置. def find_lcsubstr(s1, s2): m=[[0 for i in range(len(s2)+1)] for j in range(len(s1)+1)] #生成0矩阵,为方便后续计算,比字符串长度