蓝桥杯第八届第六题标题：最大公共子串

先不说这道题的本身

先说这道题运用的算法是什么，这道一运用的算法是动态规划。动态规划久和分治法有相似之处。当时对他规划划分的小问题会有重叠，为了避免反复的计算这些小问题。我们把每一个小问题计算的结果存放起来。更加详细的动态规划的学习，可能还需要真机找资料慢慢的理解。下面我就自己的理解，来分析一下怎么求最大公共子串。

先看一下我们老师上课用的ppt

把两个子串的公共子串的长度存在一个二维数组里面

先假设两字符串为a b

c[i][j]代表的是字符串a长度到i和字符串b长度到j ，他们公共的最长长度为从c[i][j],这样子就化成了一个比较问题相同的小问题。

b[i][j]表示的是最长长度的轨迹

如果a[i]==b[j]那么它就对于1

如果c[i-1][j]>=c[i][j-1] b[i][j]=2

否则 b[i][j]=3

蓝桥杯第八届第六题标题：最大公共子串

下面就是我写的代码

#include <stdio.h>
#include <string.h>
#include<string>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
#define N 256
int c[100][100];
int a[100][100];
int b[100][100];
char z[100];
int f(const char* s1, const char* s2)
{

   int len1 = strlen(s1);
   int len2 = strlen(s2);
   int i,j;
   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] = a[i-1][j-1]+1;//表示现在的最长公共子串长度
               b[i][j]=1;//代表最是对角线轨迹
               if(a[i][j] > max) max = a[i][j];
           }
           else if(a[i-1][j]>=a[i][j-1])
           {
           a[i][j]=a[i-1][j];
           b[i][j]=2;
           }
           else
{
a[i][j]=a[i][j-1];
b[i][j]=3;
}
       }
   }

return max;
}

int main()
{
memset(a,0,sizeof(int)*100*100);
memset(c,0,sizeof(int)*100*100);
memset(b,0,sizeof(int)*100*100);
string frist="abcd";
string secode="baabcdadabc";
   printf("%d\n", f("abcdkkk", "baabcdadabc"));
   int len1 = strlen("abcdkkk");
   int len2 = strlen("baabcdadabc");
   int k=f("abcdkkk", "baabcdadabc");
   int k2=k;
   while(len1>0&&len2>0)//求公共子串
{
if(b[len1][len2]==1)
{
z[k]=frist[len1-1];

k--;
len1--;
len2--;

}
else if(b[len1][len2]==2)
{
len1--;
}
else
{
len2--;
}
}
int i=1;
for(;i<=k2;i++)
{
cout<<z[i];
}
return 0;
}

所以这道题的写起来就很容易了

答案是a[i-1][j-1]+1

运行出来公共长度为4
标题：最大公共子串

最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。

比如："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;
}

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

蓝桥杯 第八届 第六题 标题：最大公共子串

相关推荐

蓝桥杯第八届第六题标题：最大公共子串