深入解析最长公共子串
来源：本站原创|时间：2020-01-10|栏目：C语言|点击： 次
题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。
例如：输入两个字符串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;
}
程序的效果图如下：
您可能感兴趣的文章
- 01-10深入理解约瑟夫环的数学优化方法
- 01-10深入二叉树两个结点的最低共同父结点的详解
- 01-10数据结构课程设计- 解析最少换车次数的问题详解
- 01-10深入理解C++中常见的关键字含义
- 01-10深入Main函数中的参数argc,argv的使用详解
- 01-10深入第K大数问题以及算法概要的详解
- 01-10深入理解链表的各类操作详解
- 01-10深入N皇后问题的两个最高效算法的详解
- 01-10深入理解二叉树的非递归遍历
- 01-10深入全排列算法及其实现方法
阅读排行
本栏相关
- 04-02c语言函数调用后清空内存 c语言调用
- 04-02func函数+在C语言 func函数在c语言中
- 04-02c语言的正则匹配函数 c语言正则表达
- 04-02c语言用函数写分段 用c语言表示分段
- 04-02c语言中对数函数的表达式 c语言中对
- 04-02c语言编写函数冒泡排序 c语言冒泡排
- 04-02c语言没有round函数 round c语言
- 04-02c语言分段函数怎么求 用c语言求分段
- 04-02C语言中怎么打出三角函数 c语言中怎
- 04-02c语言调用函数求fibo C语言调用函数求
随机阅读
- 04-02jquery与jsp,用jquery
- 08-05DEDE织梦data目录下的sessions文件夹有什
- 01-10SublimeText编译C开发环境设置
- 01-10C#中split用法实例总结
- 01-11ajax实现页面的局部加载
- 08-05织梦dedecms什么时候用栏目交叉功能？
- 01-11Mac OSX 打开原生自带读写NTFS功能(图文
- 08-05dedecms(织梦)副栏目数量限制代码修改
- 01-10delphi制作wav文件的方法
- 01-10使用C语言求解扑克牌的顺子及n个骰子