第八届蓝桥杯java b组第六题
2024-09-01 10:16:23
标题:最大公共子串
最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。
比如:"abcdkkk" 和 "baabcdadabc",
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路,并补全划线部分缺失的代码
/蓝桥杯第六题
public class Main {
static int f(String s1, String s2) {
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray(); int[][] a = new int[c1.length + 1][c2.length + 1]; int max = 0;
for (int i = 1; i < a.length; i++) {
for (int j = 1; j < a[i].length; j++) {
if (c1[i - 1] == c2[j - 1]) {
a[i][j]=a[i-1][j-1]+1;// 填空
//这个地方重点注意斜对角的二维数组 然后查看斜对角 那个更长
if (a[i][j] > max)
max = a[i][j];
}
}
} return max;
} public static void main(String[] args) {
int n = f("abcdekkk", "baabcdadabcd");
System.out.println(n);
}
}
最新文章
- memcache+magent的高可用
- 深度讲解VIEWPORT和PX是什么?移动端单位px,em,rem
- Bootstrap modal垂直居中
- Qt之WebKit学习之绘图
- MySQL安装过程net start mysql 启动失败 报“错误2,系统找不到文件”的解决办法
- 内核移植和文件系统制作(3)Ramdisk简介和常见问题
- QQ空间开放平台开发教程-SDK和API的使用
- ubuntu用终端卸载软件
- 开发中/listfile.jsp(11,31) quote symbol expected 这个错误
- spring 配置文件 数据库引入
- URAL1523(dp+树状数组)
- effective c++ 条款10 handle assignment to self operator =
- 【转载】Stack Overflow: The Architecture - 2016 Edition
- PCMM(人力资源能力成熟度模型)V2.0中英对照版发布
- 批处理启动vm虚拟机服务 vm12启动无界面启动vm虚拟机系统 windows上如何操作服务 sc net启动关闭服务
- Armitage攻击winxp——P201421410029
- textarea 赋值的方法
- scala文件读取报错“java.nio.charset.MalformedInputException: Input length = 1”
- mysql explain中的type列含义和extra列的含义
- WD backup西部盘数据备份
热门文章
- 纯css、js 的H5页面对接echarts
- 云原生生态周报 Vol. 17 | Helm 3 发布首个 beta 版本
- Android Studio安卓学习笔记(二)Android项目结构
- 简单的 Python 人脸识别实例
- Luogu-P1027 Car的旅行路线 已知三点确定矩形 + 最短路
- hihocoder #1616 : 是二叉搜索树吗?(模拟题)
- Codeforces Round #481 (Div. 3) A. Remove Duplicates
- Codeforces 734C. Anton and Making Potions(二分)
- Docker笔记(十):使用Docker来搭建一套ELK日志分析系统
- JS-特效 ~ 02. 屏幕滚动事件、 DTD、scroll、顶部悬浮导航、两侧跟随广告、返回顶部小火煎