2017蓝桥杯最大公共子串(C++B组)
题目:
最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。
比如:"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;
}
注意:只提交缺少的代码,不要提交已有的代码和符号。也不要提交说明性文字。
解析:
刚开始挺纳闷的,这种问题太简单了, 为啥要用矩阵增加其难度呢,本来设置一个常规变量注意好初始化和改变的位置就行了,如果这个问题是编程题,我相信99%的人可以很快做出来,当我刚看到这道题的时候,我想,难道还需要利用数组下标赋值字符么,这是一种什么思维,后来毛瑟顿开,该程序一开始利用memset函数将临时数组的全部元素都初始化为0,这是一个信号,一个非常重要的信号,后来又用双重for循环遍历全部数组元素,细心的同学或许注意到了一点,两个for语句都是从 1 循环的,并不是从数组本有特性 0 开始循环,这又是一个信号(如果不这样做,关键的一句代码就会造成数组越界),它要利用字符串的特性-具有连接性并且结合临时数组全部为0的特性更简单更高效的把最大公共子串的长度给求出来!
#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] = a[i-1][j-1] + 1;
if(a[i][j] > max)
max = a[i][j];
}
}
}
return max;
}
int main()
{
printf("%d\n", f("abcdkkk", "baabcdadabc"));
return 0;
}
最新文章
- 洛谷 P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers Label:ExWater
- Gobblin编译支持CDH5.4.0
- openstack-lanch an instance and nova compute log analysis
- 系统无法开始服务器进程。请检查用户名和密码。 (Exception from HRESULT: 0x8000401A)
- Sla子分类账表结构
- iOS手机功能汇总
- MQTT V3.1--我的理解
- 使用RestTemplate Spring安全认证
- socket.io遇到的问题
- Lua脚本之语法基础快速入门
- acmer -- 最美的情书
- HDU3415:Max Sum of Max-K-sub-sequence(单调队列)
- 14.3.3 Locks Set by Different SQL Statements in InnoDB 不同的SQL语句在InnoDB里的锁设置
- LoadRunner监控Unix、Windows方法及常用性能指标
- CF666E Forensic Examination
- Centos7.4 防火墙配置
- github/gitee使用办法2
- array_walk 与 array_map的 区别
- linux --- 10.常见命令
- C-Lodop获取打印机列表Create_Printer_List
热门文章
- 【Python】pyinstaller打包运行报错failed to execute script main
- 【Weiss】【第03章】练习3.4、3.5:有序链表求交、并
- 原创】Java并发编程系列2:线程概念与基础操作
- iOS 原生库(AVFoundation)实现二维码扫描,封装的工具类,不依赖第三方库,可高度自定义扫描动画及界面(Swift 4.0)
- JavaScript和JSCript的标准ECMAScript
- Topshelf+Quartz3.0基于控制台应用程序快速开发可调度windows服务
- HTML中的IE条件注释,让低版本IE也能正常运行HTML5+CSS3网站的3种解决方案
- AdFind
- VS code调试代码快速上手必备知识
- 洛谷 P1891 疯狂LCM 题解