第八届蓝桥杯最大公共子串（动态规划）

本文主要是介绍第八届蓝桥杯最大公共子串（动态规划），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

标题：最大公共子串

最大公共子串长度问题就是：

求两个串的所有子串中能够匹配上的最大长度是多少。

比如："abcdkkk" 和 "baabcdadabc"，

可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。

下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。

请分析该解法的思路，并补全划线部分缺失的代码。

#include <stdio.h>
#include <string.h>

#define N 256
int f(const char* s1, const char* s2)
{
int a[N][N];
int len1 = strlen(s1);
int len2 = strlen(s2);
int i,j;

memset(a,0,sizeof(int)*N*N);
int max = 0;
for(i=1; i<=len1; i++){
for(j=1; j<=len2; j++){
if(s1[i-1]==s2[j-1]) {
a[i][j] = __________________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}

return max;
}

int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
}

注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。

观察可以看出该题的代码是动态规划的类型；

子问题：第一个字符串中以i结尾的字符串和第二个字符串中以j结尾的字符串的最长公共子串的长度；

状态：dp[i][j]表示第一个字符串中以i结尾的字符串和第二个字符串中以j结尾的字符串的最长公共子串的长度；

状态转移方程：考虑状态方程要结合子问题来考虑。如果str1[i]==str2[j],这时dp[i][j]就可以从dp[i-1][j-1]转移过来。

如果str1[i]，str2[j]不相等的话，状态就不转移，或者dp[i][j]为0，二者是等价的。因为我们要考虑到后来的状态可能会从当前状态转移过来，例如当str1[i]!=str2[j]，str[i+1]=str[j+1]时，dp[i][j]=0,dp[i+1][j+1]=dp[i][j]+1。符合连续子串的定义。、

正是因为这个性质，所以最长公共子串的最大值不一定是在dp[len1][len2]中，所以我们要用一个变量来存这个最大值。

答案为a[i-1][j-1]+1;

——————————————————————————————————————————————————

接下来我们考虑另一个问题，如何输出最长公共子串。

因为最长公共子串的不唯一，我们可以用一个数组CoordinateMax来存最长公共子串的末尾的字符在第一个字符串和第二个字符串的下标。在动态规划过程中，如果max发生了更新，我们就更新CoordinateMax最后一个存有实际内容元素的值。

当max == dp[i][j],说明在当前子问题中存在多个长度相同的最长公共子串，我们就在CoordinateMax中加入该点信息

代码如下

#include<stdio.h>
#include<string.h>const int INF = 1005;int CoordinateMax[100][2], index = 0, max = -1;int LongestCommonSubstring(char* str1, char* str2, int len1, int len2);int dp[INF][INF] = {0};
/*
abcdkkkkedydfghfs
baabcdadabckkkksgsdghdghfsjgh
*/
int main()
{char str1[INF],  str2[INF];scanf("%s",str1);scanf("%s",str2);int len1 = strlen(str1), len2 = strlen(str2);LongestCommonSubstring(str1,str2,len1,len2) ;printf("%d\n",max);return 0;
} 
int LongestCommonSubstring(char* str1, char* str2, int len1, int len2)
{for(int i = 1; i <= len1; i++){for(int j = 1; j <= len2; j++){if(str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;if(max < dp[i][j]){max = dp[i][j];CoordinateMax[index][0] = i, CoordinateMax[index][1] = j;			//当max更新时，CoordiateMax也需要更新（注意不是添加一个元素） }else if(max == dp[i][j]){index++;CoordinateMax[index][0] = i, CoordinateMax[index][1] = j;			//当max与dp[i][j]相等时，说明在当前子问题中存在多个最长公共子串，//我们需要在CoordinateMax中添加该点的信息 }}}} for(int i = index; i >= 0; i--){if(dp[CoordinateMax[i][0]][CoordinateMax[i][1]] == max){int end1 = CoordinateMax[i][0]; for(int i = end1-max; i < end1; i++)printf("%c",str1[i]);printf("\n");}elsebreak;}return max;}