专栏首页Debug客栈蓝桥杯-2017年省赛C++B组题6-最大公共子串

蓝桥杯-2017年省赛C++B组题6-最大公共子串

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

比如:”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;
}

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

代码答案

a[i-1][j-1] + 1

本文链接:https://www.debuginn.cn/2419.html

本文采用CC BY-NC-SA 3.0 Unported协议进行许可,转载请保留此文章链接

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 蓝桥杯 基础练习 杨辉三角形

    输出杨辉三角形的前n行。每一行从这一行的第一个数开始依次输出,中间使用一个空格分隔。请不要在前面输出多余的空格。

    Debug客栈
  • 蓝桥杯 基础练习 数列排序

    第一行为一个整数n。 第二行包含n个整数,为待排序的数,每个整数的绝对值小于10000。

    Debug客栈
  • 蓝桥杯 基础练习 回形取数

      回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转90度。一开始位于矩阵左上角,方向向下。输入格式  输入第一行是两个不超过200的正整数m...

    Debug客栈
  • 2018 团队设计天梯赛题解---华山论剑组

    2018 年度的团队设计天梯赛前几天结束了。但是成绩真的是惨不忍睹。。。毕竟是团队的比赛,如果团队平均水平不高的话,单凭一个人,分再高也很难拉起来(当然,一个人...

    指点
  • 1的个数

    小南刚学了二进制,他想知道一个数的二进制表示中有多少个1,你能帮他写一个程序来完成这个任务吗?

    书童小二
  • 1501 二叉树最大宽度和高度

    1501 二叉树最大宽度和高度 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 白银 Silver 题目描述 Descripti...

    attack
  • 吉林大学考研复试题目(牛客网)

    ​ 一个二进制数,将其每一位取反,称之为这个数的反码。下面我们定义一个字符的反码。如果这是一个小写字符,则它和字符'a’的距离与它的反码和字符'z’的距离相同;...

    Kindear
  • 【USACO 3.2】Magic Squares

    4*2个格子分别为 1234 8765 的魔板有3种操作,A:上下两排互换,B:最后一列放到第一列前面,C:中间四个顺时针旋转1格。 现在给出目标状态,...

    饶文津
  • 数据结构和算法——动态规划

    一、动态规划的思想     动态规划(dynamic programming)是一种算法设计的思想,主要是将一个问题划分成几个更小的问题,并对这样更小的问题进行...

    zhaozhiyong
  • 算法-编程的灵魂--八皇后

    对于我们程序员来说,算法是编程的灵魂,算法的好坏与否,也决定了你代码的健壮性。 ----至此,祝愿各位五一节快乐,玩的开心! 下面,看看下面的经典算法,经典的算...

    赵腰静

扫码关注云+社区

领取腾讯云代金券