最长公共子字符串的使用分析

子字符串的定义和子串的定义类似,但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB,它们的长度都是2。
最长公共子字符串共有两种解决方法,下面具体说说我的思路
方法一:
Longest Common Substring和Longest Common Subsequence是有区别的
X = <a, b, c, f, b, c>
Y = <a, b, f, c, a, b>
X和Y的Longest Common Sequence为<a, b, c, b>,长度为4
X和Y的Longest Common Substring为 <a, b>长度为2
其实Substring问题是Subsequence问题的特殊情况,也是要找两个递增的下标序列
<i1, i2, ...ik> 和 <j1, j2, ..., jk>使
xi1 == yj1
xi2 == yj2
......
xik == yjk
与Subsequence问题不同的是,Substring问题不光要求下标序列是递增的,还要求每次
递增的增量为1, 即两个下标序列为:
<i, i+1, i+2, ..., i+k-1> 和 <j, j+1, j+2, ..., j+k-1>
类比Subquence问题的动态规划解法,Substring也可以用动态规划解决,令
c[i][j]表示Xi和Yi的最大Substring的长度,比如
X = <y, e, d, f>
Y = <y, e, k, f>
c[1][1] = 1
c[2][2] = 2
c[3][3] = 0
c[4][4] = 1
动态转移方程为:
如果xi == yj, 则 c[i][j] = c[i-1][j-1]+1
如果xi ! = yj,  那么c[i][j] = 0
最后求Longest Common Substring的长度等于
max{  c[i][j],  1<=i<=n, 1<=j<=m}
 完整的代码如下:


代码如下:

/**
找出两个字符串的最长公共连续子串的长度
** author :liuzhiwei 
** data:2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
 int i,j,k,len1,len2,max,x,y;
 len1 = strlen(str1);
 len2 = strlen(str2);
 int **c = new int*[len1+1];
 for(i = 0; i < len1+1; i++)
  c[i] = new int[len2+1];
 for(i = 0; i < len1+1; i++)
  c[i][0]=0;//第0列都初始化为0
 for(j = 0; j < len2+1; j++)
  c[0][j]=0;//第0行都初始化为0
 max = -1;
 for(i = 1 ; i < len1+1 ; i++)
 {
  for(j = 1; j < len2+1; j++)
  {
   if(str1[i-1]==str2[j-1])//只需要跟左上方的c[i-1][j-1]比较就可以了
    c[i][j]=c[i-1][j-1]+1;
   else//不连续的时候还要跟左边的c[i][j-1]、上边的c[i-1][j]值比较,这里不需要
    c[i][j]=0;
   if(c[i][j]>max)
   {
    max=c[i][j];
    x=i;
    y=j;
   }
  }
 }
 //输出公共子串
 char s[1000];
 k=max;
 i=x-1,j=y-1;
 s[k--]='\0';
 while(i>=0 && j>=0)
 {
  if(str1[i]==str2[j])
  {
   s[k--]=str1[i];
   i--;
   j--;
  }
  else  //只要有一个不相等,就说明相等的公共字符断了,不连续了
   break;
 }
 printf("最长公共子串为:");
 puts(s);
 for(i = 0; i < len1+1; i++)//释放动态申请的二维数组
  delete[] c[i];
 delete[] c;
 return max;
}
int main(void)
{
 char str1[1000],str2[1000];
 printf("请输入第一个字符串:");
 gets(str1);
 printf("请输入第二个字符串:");
 gets(str2);
 int len = longest_common_substring(str1, str2);
 printf("最长公共连续子串的长度为:%d\n",len);
 system("pause");
 return 0;
}

效果图如下: 

方法二:
将字符串s1和s2分别写在两把直尺上面(我依然用s1,s2来表示这两把直尺),然后将s1固定,s2的头部和s1的尾部对齐,然后逐渐移动直尺s2,比较重叠部分的字符串中的公共子串的长度,直到直尺s2移动到s1的头部。在这个过程中求得的最大长度就是s1、s2最大子串的长度。
下图是求解过程的图示(下图有点错误,应该是将s2从右往左移动),蓝色部分表示重叠的字符串,红色的部分表示重叠部分相同的子串
其中s1="shaohui",s2="ahui",最后求得的结果为3

完整的代码如下:


代码如下:

/**
找出两个字符串的最长公共连续子串的长度
** author :liuzhiwei 
** data   :2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
 int i,len1,len2,len,s1_start,s2_start,idx,curmax,max;
 len1 = strlen(str1);
 len2 = strlen(str2);
 len = len1 + len2;
 max = 0;
 for(i = 0 ; i < len ; i++)
 {
  s1_start = s2_start = 0;
  if(i < len1)
   s1_start = len1 - i;    //每次开始匹配的起始位置
  else
   s2_start = i - len1;
  curmax = 0;
  for(idx = 0 ; ( s1_start + idx < len1 ) && ( s2_start + idx < len2 ); idx++ )
  {
   if(str1[s1_start+idx]==str2[s2_start+idx])
    curmax++;
   else     //只要有一个不相等,就说明相等的公共字符断了,不连续了,要保存curmax与max中的最大值,并将curmax重置为0
   {
    max = curmax > max ? curmax : max;
    curmax = 0;
   }
  }
  max = curmax > max ? curmax : max;
 }
 return max;
}
int main(void)
{
 char str1[1000],str2[1000];
 printf("请输入第一个字符串:");
 gets(str1);
 printf("请输入第二个字符串:");
 gets(str2);
 int len = longest_common_substring(str1, str2);
 printf("最长公共连续子串的长度为:%d\n",len);
 system("pause");
 return 0;
}

效果图如下:

稍微改动一下,便可以输出公共子串了,就是要保存一下连续公共子串最后一个字符在其中一个字符串中的下标位置:


代码如下:

/**
找出两个字符串的最长公共连续子串的长度
** author :liuzhiwei 
** data   :2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
int longest_common_substring(char *str1, char *str2)
{
 int i,k,len1,len2,len,s1_start,s2_start,idx,curmax,max;
 len1 = strlen(str1);
 len2 = strlen(str2);
 len = len1 + len2;
 max = 0;
 for(i = 0 ; i < len ; i++)
 {
  s1_start = s2_start = 0;
  if(i < len1)
   s1_start = len1 - i;    //每次开始匹配的起始位置
  else
   s2_start = i - len1;
  curmax = 0;
  for(idx = 0 ; ( s1_start + idx < len1 ) && ( s2_start + idx < len2 ); idx++ )
  {
   if(str1[s1_start+idx]==str2[s2_start+idx])
    curmax++;
   else     //只要有一个不相等,就说明相等的公共字符断了,不连续了,要保存curmax与max中的最大值,并将curmax重置为0
   {
    //max = curmax > max ? curmax : max;
    if(curmax > max)
    {
     max = curmax;
     k = s1_start+idx-1;      //保存连续子串长度增加时连续子串最后一个字符在str1字符串中的下标位置,便于输出公共连续子串
    }
    curmax = 0;
   }
  }
  //max = curmax > max ? curmax : max;
  if(curmax > max)
  {
   max = curmax;
   k = s1_start+idx-1;
  }
 }
 //输出公共子串
 char s[1000];
 for(i=0;i<max;i++)
  s[i]=str1[k-max+1+i];     //公共字串在str1中的下标起始位置为k-max+1,结束位置为k
 s[i]='\0';
 printf("最长公共子串为:");
 puts(s);
 return max;
}
int main(void)
{
 char str1[1000],str2[1000];
 printf("请输入第一个字符串:");
 gets(str1);
 printf("请输入第二个字符串:");
 gets(str2);
 int len = longest_common_substring(str1, str2);
 printf("最长公共连续子串的长度为:%d\n",len);
 system("pause");
 return 0;
}

效果图如下:

扩展:子串也可以是反串,比如HDOJ 1238
题目意思是要搜索最长的子串
给出一系列字符串,几个子串可以是反串
rose
orchid 
这里最长的子串是 ro 跟or 长度为2。
如果穷举搜索的话,肯定过不了。
所以可以找出所有字符串中最短的串,枚举最短的字符串的子串
判断是否都是别的字符串的子串,求出最大长度即可。。


代码如下:

/**
找出两个字符串的最长公共连续子串的长度
** author :liuzhiwei 
** data   :2011-08-16
**/
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
char str[100][100];
int k;
int match(int start,int end,int n)   //最短字符串中的起点下标、终点下标,字符串总数
{
 int i,j,len,p,h;
 for(i=0;i<n;i++)
 {
  if(i==k)
   continue;
  len=strlen(str[i]);
  for(j=0;j<=len-1-end+start;j++)    //str[i]字符串可以组成len-1-end+start个长度为end-start的连续子串
  {
   for(p=start,h=j;p<=end;p++,h++)    //顺序判断子串
   {
    if(str[k][p]!=str[i][h])       //不等即跳出
     break;
   }
   if(p>end)                   //如果全部相等,则匹配成功,终止
    break;
   for(p=end,h=j;p>=start;p--,h++)             //逆序判断子串
   {
    if(str[k][p]!=str[i][h])       //不等即跳出
     break;
   }
   if(p<start)                   //如果全部相等,则匹配成功,终止
    break;
  }
  if(j>len-1-end+start)    //如果搜索完毕都没终止,即无匹配
   return 0;
 }
 return 1;
}
int main(void)
{
 int t,i,j,n,len,minlen,flag;
 scanf("%d",&t);
 while(t--)
 {
  minlen=1000,flag=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
   scanf("%s",str[i]);
   len = strlen(str[i]);
   if(len<minlen)
   {
    minlen=len;      //保存最短字符串的长度
    k=i;             //保存最短字符串的序号
   }
  }
  for(i=0;i<minlen;i++)    //对最短字符串的连续字串进行匹配查找
  {
   for(j=0;j<=i;j++)
   {
    if(match(j,j+minlen-1-i,n))    //子串是否匹配
    {
     flag=1;
     break;
    }
   }
   if(flag==1)
    break;
  }
  printf("%d\n",minlen-i);
 }
 system("pause");
 return 0;
}

(0)

相关推荐

  • 最长公共子字符串的使用分析

    子字符串的定义和子串的定义类似,但要求是连续分布在其他字符串中.比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB,它们的长度都是2.最长公共子字符串共有两种解决方法,下面具体说说我的思路方法一:Longest Common Substring和Longest Common Subsequence是有区别的X = <a, b, c, f, b, c>Y = <a, b, f, c, a, b>X和Y的Longest Common Sequence为<a

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

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

  • C语言求解最长公共子字符串问题及相关的算法分析

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串.注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中.请编写一个函数,输入两个字符串,求它们的最长公共子序列,并打印出最长公共子序列. 例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子序列,则输出它们的长度4,并打印任意一个子序列. 分析:求最长公共子序列(Longest Common Subsequence, LCS)是一道非常经典的

  • 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,

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

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

  • 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

  • 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

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

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

  • PHP实现求两个字符串最长公共子串的方法示例

    本文实例讲述了PHP实现求两个字符串最长公共子串的方法.分享给大家供大家参考,具体如下: 前面一篇PHP实现求解最长公共子串问题的方法是基于java改进而来,这里再来看另一种公共子串算法. 代码如下: <?php $a = 'abceee12345309878'; $b = 'abceeew2345i09878fsfsfsfabceeewsfsdfsfsabceeew'; $c = array(); $lenht1 = strlen($a); $lenth2 = strlen($b); $sta

随机推荐