Java实现第八届蓝桥杯最大公共子串
JAVA 实现 蓝桥 最大 公共 子串 第八届
2023-09-14 08:58:11 时间
最大公共子串
最大公共子串长度问题就是:
求两个串的所有子串中能够匹配上的最大长度是多少。
比如:“abcdkkk” 和 “baabcdadabc”,
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的,这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路,并补全划线部分缺失的代码。
这个有点dp的意思,分别计算两个字符串每一个字符到另一个字符是否相等 若相等 则加前面字符的最大字符串 若前面字符也分别相等则他就等于a[i-1][j-1]+1 若不想等则为0+1
public class 最大公共子串 {
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("abcdkkk", "baabcdadabc");
System.out.println(n);
}
}
相关文章
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- java:BeanProperSupport实现复杂类型对象的成员访问
- Java重置_java设置定时任务一小时执行一次
- Java 实现数据库读写分离竟如此简单?
- java 舆情分析_基于Java实现网络舆情分析系统研究与实现.doc[通俗易懂]
- java+sm4+加密算法_SM4加密算法实现Java和C#相互加密解密
- java实现联机五子棋详解编程语言
- 通过Java NIO 实现文件下载详解编程语言
- Java实现RC5算法详解编程语言
- A星算法Java实现详解编程语言
- 实现Java程序操作MySQL数据库(java调用mysql)
- Java实现MSSQL数据库连接(java连接mssql)
- 清理使用Java实现Redis数据定时清理(redisjava过期)
- 机制Redis Java实现的过期清理机制(redisjava过期)
- Redis与Java实现数据过期管理(redisjava过期)
- Java实现Redis数据写入(java写入redis)
- Java调用Redis实现高性能数据存储(java调用redis)
- Java轻松处理Redis缓存(java处理redis)
- Java编程实现MySQL表备份(java备份mysql表)
- 实现高并发:Java利用Redis秒杀成功(java秒杀redis)
- Java实现与Oracle数据库的无缝整合(java整合oracle)
- Oracle中实现Java程序设计的极限可能性(oracle中的java)