最长公共子串问题-创新互联

我的解题思路：

创新互联公司是一家专业提供洛龙企业网站建设,专注与做网站、网站制作、H5开发、小程序制作等业务。10年已为洛龙众多企业、政府机构等服务。创新互联专业网站设计公司优惠进行中。

 生成动态规划表，即大小为M*N的矩阵dp（M和N分别是两个字符串的长度）；

求dp[i][j]过程：

 1.矩阵第一列即dp[0~M-1][0],对某一个位置（i，0）来说，如果str1[i]==str2[0],令dp[i][0]=1,.否则令dp[i][0]=0;

 2.矩阵第一行即dp[0][0~N-1]，对某一个位置（0，j）来说，如果str1[0]==str2[j],令dp[0][j]=1,.否则令dp[i][0]=0;

 3.其余位置按照从左到右，从上到下位置计算，dp[i][j]的值只可能有两种情况：

    a.如果str1[i]!=str2[j],说明在必须把str1[i]和str2[j]当做公共子串的最后一个字符是不可能的，令dp[i][j]=0;

    b.如果str1[i]==str2[j],说明str1[i]和str2[j]可以当做公共子串的最后一个字符，dp[i][j]=dp[i-1][j-1]+1;

生成动态规划表后，表里面大的数字就是公共子串的长度

下面是具体的代码：

#include <iostream>

#include <string>

using namespace std;

int dp[8][8] = { 0 };//二维矩阵大小自己定义，保证能容下字符串就行

void initdp(char *str1, char *str2)

{

int len1 = strlen(str1);

int len2 = strlen(str2);

for (int i = 0; i < len1; i++)

{

if (str1[i] == str2[0])

{

dp[i][0] = 1;

}

}

for (int j = 1; j < len2; j++)

{

if (str2[j] == str1[0])

{

dp[0][j] = 1;

}

}

for (int i = 1; i < len1; i++)

{

for (int j = 1; j < len2; j++)

{

if (str1[i] == str2[j])

{

dp[i][j] = dp[i - 1][j - 1] + 1;

}

}

}

}

void MaxChar(char *str1, char *str2)

{

int len1 = strlen(str1);

int len2 = strlen(str2);

int max = 0;

int end = 0;

for (int i = 0; i < len1; i++)

{

for (int j = 0; j < len2; j++)

{

if (dp[i][j]>max)

{

max = dp[i][j];

end = i;

}

}

}

for (int i = end - max+1; i <= end; ++i)

{

printf("%c", str1[i]);

}

printf("\n");

}

int main()

{

char *str1 = "ab123cd";

char *str2 = "db1234cg";

initdp(str1, str2);

MaxChar(str1, str2);

return 0;

}

如果哪位大神还有更好的方法请给小生说下，谢谢啦

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。

当前文章：最长公共子串问题-创新互联
本文来源：https://www.cdcxhl.com/article20/cciijo.html

成都网站建设公司_创新互联，为您提供用户体验、商城网站、标签优化、企业网站制作、响应式网站、云服务器

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联