2022.6.4最长公共子串
【问题描述】
给定两个字符串，求出它们两个最长的相同子字符串的长度。
最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值。同学们不应该单单只是写出该问题的基本解决代码而已，关键还是享受把算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。
【输入形式】两个字符串
【输出形式】最长的公共子串，若没有则输出“no”
【样例输入】acbcbcef
abcbced
【样例输出】bcbce
【温馨提示】问题的关键不在于提交代码并通过测试数据，而是你是否真正掌握了所有求解的算法。
法一：暴力枚举法（即进行一一比较，得出最长的子串长度与起点后，进行输出）
代码如下：
#include
#include
#define Maxsize 1000
using namespace std;int main()
{char a[Maxsize],b[Maxsize];cin>>a>>b;int lena=strlen(a),lenb=strlen(b),Max=0,xb=0,len=0,i=0,j=0;for(i=0;i 法二：使用dp动态数组
a的长度为M，b的长度为N，生成N*M大小的数组dp[M][N]；其中dp[i][j]表示以a[i]结尾与b[j]结尾的公共子串的长度。
注意：循环中对dp数组的赋值是使用 i+1，j+1，是由于需要将 dp 数组的最左边和最上边空出来。这样赋值的时候就不需要进行判断此刻赋值的是不是 dp 数组的边界位置（最左边和最上边）
| a | b | c | t | h | i | |
|---|---|---|---|---|---|---|
| t | 0 | 0 | 0 | 1 | 0 | 0 |
| h | 0 | 0 | 0 | 0 | 2 | 0 |
| i | 0 | 0 | 0 | 0 | 0 | 3 |
代码如下：
#include #include #define Maxsize 1000using namespace std;char a[Maxsize],b[Maxsize];int dp[Maxsize][Maxsize],x=0,y=0,Max=0;void Compare(){int lena=strlen(a),lenb=strlen(b);for(int i=0;iMax){x=i+1;y=j+1;Max=dp[i+1][j+1];}} //双重for循环对dp数组进行处理//对最长子串进行输出if(Max==0) cout<<"no";else{ for(int i=x-Max;i>a>>b;Compare();return 0;} 法三：对方法二进行了空间的优化，也就是滚动数组。（即使用一维数组）
注意：滚动一维数组的时候，要从数组的最右侧开始赋值，这样便不会发生执行到dp[i+1]=dp[i]
+1这条语句的时候，dp[i]已经被修改的情况。这里使用dp[i+1]，是因为这样写便不需要判断此刻赋值的位置是否是边界位置
代码如下：
#include
#include
#define Maxsize 1000
using namespace std;char a[Maxsize],b[Maxsize];int dp[Maxsize],x=0,Max=0;void Compare()
{int lena=strlen(a),lenb=strlen(b);for(int i=0;i=0;j--){if(a[i]==b[j])dp[j+1]=dp[j]+1;elsedp[j+1]=0;if(dp[j+1]>Max){x=j+1;Max=dp[j+1];}}}if(Max==0) cout<<"no";else{for(int i=x-Max;i>a>>b;Compare();return 0;
} 法四：开个对角线大小的数组
如下表所示：
| a | b | c | t | h | i | |
|---|---|---|---|---|---|---|
| t | 0 | 0 | 0 | 1 | 0 | 0 |
| h | 0 | 0 | 0 | 0 | 2 | 0 |
| i | 0 | 0 | 0 | 0 | 0 | 3 |
（1）分成两部分进行求解，即左下与右上部分。
这样子需要写两个双重循环，比较麻烦；并且Compare函数具有局限性，也就是，只可以适用于数组a的长度大于数组b的长度的情形，需要在主函数调用该函数时进行判断
代码如下：
#include
#include
#define Maxsize 1000
using namespace std;int dp[Maxsize],x=0,Max=0;void Compare(char a[],char b[])
{int lena=strlen(a),lenb=strlen(b),i,j,n;for(n=0;n=0&&i<=n;i++,j++){if(a[i]==b[j]) dp[i+1]=dp[i]+1;else dp[i+1]=0;if(dp[i+1]>Max){x=i+1;Max=dp[i+1];}}}//左下部分for(n=lena-1;n>=0;n--){//n控制第一个字符串和第二个字符串结束遍历的位置for(i=n,j=0;j<=i-n&&iMax){x=i+1;Max=dp[i-n+1];}}}//右上部分if(Max==0) cout<<"no";else{for(int i=x-Max;i>a>>b;//在此处进行判断，将数组长度较长的那一个放到左边的参数位置if(strlen(a)>strlen(b)) Compare(a,b);else Compare(b,a);return 0;
} （2）不分成两部分，直接一个双重循环进行求解
整体从右上部分开始向左下方向移动，其中每一次对角线比较是从左上到右下
代码如下：
#include
#include
#define Maxsize 1000
using namespace std;char a[Maxsize],b[Maxsize];int dp[Maxsize],x=0,Max=0;void Compare()
{int lena=strlen(a),lenb=strlen(b);int m=lena-1,n=0;//分别控制第一个和第二个字符串结束遍历的位置for(;nMax){Max=dp[k+1];x=i+1;}}if(m!=0) m--;else n++;}if(Max==0) cout<<"no";else{for(int i=x-Max;i>a>>b;Compare();return 0;
} 法五：不用开数组
这种方法实际上就是沿着对角线进行判断、计数。既可以看作是法四的优化，也就是将法四中的一维数组的空间简化为一个int型的空间；也可以看作是法一的优化，将时间复杂度进行了优化
#include
#include
#define Maxsize 1000
using namespace std;char a[Maxsize],b[Maxsize];int dp,x=0,Max=0;void Compare()
{int lena=strlen(a),lenb=strlen(b);int m=lena-1,n=0;//分别控制第一个和第二个字符串结束遍历的位置for(;nMax){Max=dp;x=i+1;}}if(m!=0) m--;else n++;}if(Max==0) cout<<"no";else{for(int i=x-Max;i>a>>b;Compare();return 0;
} 注：以上仅仅是作业提交通过的代码，如有其他错误或者是可以进一步优化的地方，欢迎指出
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！