最长公共子串问题
我的解题思路：
创新互联建站专注于呼兰企业网站建设,成都响应式网站建设公司,商城网站建设。呼兰网站建设公司,为呼兰等地区提供建站服务。全流程按需求定制设计，专业设计，全程项目跟踪，创新互联建站专业和态度为您提供的服务
生成动态规划表，即大小为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
#include
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;
}
如果哪位大神还有更好的方法请给小生说下，谢谢啦
网页名称：最长公共子串问题
本文网址：http://hbruida.cn/article/jegccp.html
