最长公共子字符串的使用分析
更新时间：2020年4月25日 17:47 点击：2088
子字符串的定义和子串的定义类似，但要求是连续分布在其他字符串中。比如输入两个字符串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;
}
效果图如下：
题目意思是要搜索最长的子串
给出一系列字符串,几个子串可以是反串
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;
}
最长公共子字符串共有两种解决方法，下面具体说说我的思路
方法一：
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;
}
效果图如下：
题目意思是要搜索最长的子串
给出一系列字符串,几个子串可以是反串
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;
}
上一篇: 如何正确的使用语句块
下一篇: 深入理解C语言中编译相关的常见错误
相关文章
- 本篇文章是对最长公共子字符串的使用进行了详细的分析介绍，需要的朋友参考下...2020-04-25