最长公共子字符串的使用分析
使用 分析 字符串 最长 公共
2023-06-13 09:14:59 时间
子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串BDCABA和ABCBDAB的最长公共字符串有BD和AB，它们的长度都是2。
最长公共子字符串共有两种解决方法，下面具体说说我的思路
方法一：
LongestCommonSubstring和LongestCommonSubsequence是有区别的
X=<a,b,c,f,b,c>
Y=<a,b,f,c,a,b>
X和Y的LongestCommonSequence为<a,b,c,b>，长度为4
X和Y的LongestCommonSubstring为<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
最后求LongestCommonSubstring的长度等于
max{ c[i][j], 1<=i<=n，1<=j<=m}
完整的代码如下：
复制代码代码如下:
方法一：
X=<a,b,c,f,b,c>
Y=<a,b,f,c,a,b>
X和Y的LongestCommonSequence为<a,b,c,b>，长度为4
X和Y的LongestCommonSubstring为<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
最后求LongestCommonSubstring的长度等于
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"
intlongest_common_substring(char*str1,char*str2)
{
inti,j,k,len1,len2,max,x,y;
len1=strlen(str1);
len2=strlen(str2);
int**c=newint*[len1+1];
for(i=0;i<len1+1;i++)
c[i]=newint[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;
}
}
}
//输出公共子串
chars[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;
returnmax;
}
intmain(void)
{
charstr1[1000],str2[1000];
printf("请输入第一个字符串：");
gets(str1);
printf("请输入第二个字符串：");
gets(str2);
intlen=longest_common_substring(str1,str2);
printf("最长公共连续子串的长度为：%d\n",len);
system("pause");
return0;
}
效果图如下：
将字符串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"
intlongest_common_substring(char*str1,char*str2)
{
inti,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;
}
returnmax;
}
intmain(void)
{
charstr1[1000],str2[1000];
printf("请输入第一个字符串：");
gets(str1);
printf("请输入第二个字符串：");
gets(str2);
intlen=longest_common_substring(str1,str2);
printf("最长公共连续子串的长度为：%d\n",len);
system("pause");
return0;
}
效果图如下：
/**
找出两个字符串的最长公共连续子串的长度
**author:liuzhiwei
**data :2011-08-16
**/
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
intlongest_common_substring(char*str1,char*str2)
{
inti,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;
}
}
//输出公共子串
chars[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);
returnmax;
}
intmain(void)
{
charstr1[1000],str2[1000];
printf("请输入第一个字符串：");
gets(str1);
printf("请输入第二个字符串：");
gets(str2);
intlen=longest_common_substring(str1,str2);
printf("最长公共连续子串的长度为：%d\n",len);
system("pause");
return0;
}
效果图如下：
题目意思是要搜索最长的子串
给出一系列字符串,几个子串可以是反串
rose
orchid
这里最长的子串是ro跟or长度为2。
如果穷举搜索的话,肯定过不了。
所以可以找出所有字符串中最短的串,枚举最短的字符串的子串
判断是否都是别的字符串的子串，求出最大长度即可。。
/**
找出两个字符串的最长公共连续子串的长度
**author:liuzhiwei
**data :2011-08-16
**/
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
charstr[100][100];
intk;
intmatch(intstart,intend,intn) //最短字符串中的起点下标、终点下标，字符串总数
{
inti,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) //如果搜索完毕都没终止,即无匹配
return0;
}
return1;
}
intmain(void)
{
intt,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");
return0;
}
相关文章
- 数据绑定以及Container.DataItem几种方式与使用方法分析[通俗易懂]
- 4-Air724UG模块(4G全网通GPRS开发)-下载DTU固件和入门使用(使用的我的模块看这一节)
- 1. 「snabbdom@3.5.1 源码分析」snabbdom 介绍和使用
- 如何使用GPT_Vuln-analyzer并利用ChatGPT来进行网络安全分析
- 一文分析SQL Server中事务使用的锁
- 如何使用Linux查看tar压缩文件（linux查看tar文件）
- 计算使用Oracle计算人员年龄：数据日期分析（oracle日期年龄）
- 使用Linux批量重命名文件（批量重命名linux）
- 如何在 Linux 上使用 tcpdump 命令捕获和分析数据包
- 如何在 CentOS 8/RHEL 8 上安装和使用 Cockpit
- Oracle跳过操作: 如何在查询中使用Skip？（oracleskip）
- 使用SQL Server增加工作效率：搭建独立实例（sqlserver加实例）
- 降低Oracle使用成本的技巧（lower在oracle）
- 安装Redis让你使用Redis更便捷（使用redis需要安装）
- 使用Oracle R命令行分析大数据（oracle r 命令行）
- jsapply/call/caller/callee/bind使用方法与区别分析
- SQLServer高级内容之case语法函数概述及使用
- jquery中使用$(#form).submit()重写提交表单无效原因分析及解决
- 查询优化之EXPLAIN的使用分析
- 使用php检测用户当前使用的浏览器是否为IE浏览器