牛客网:最长公共子串问题
2021/6/14 18:22:24
本文主要是介绍牛客网:最长公共子串问题,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
这道题我觉得,直接二重循环,记录最大长度和相应的字符就可以。
答案思路
这里的动态规划表dp[i][j],代表了在必须以a[i],b[j]为公共子串最后一个字符时,公共子串多长。这里先判断横纵分别对应的第一列,第一行,然后如果两个字符相等,它们的值是dp[i][j] = dp[i-1][j-1] +1。不相等就是0.
答案中的优化算法是按照对角线遍历
注意对角线前进的方向,画好图再写代码
import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); char[] f_arr = scanner.nextLine().toCharArray(); char[] s_arr = scanner.nextLine().toCharArray(); int m = 0; int n = 0; int max_len = 0; int max_m = 0; int max_n = 0; int start_m = f_arr.length-1; int start_n = 0; int len = 0; while(start_m!=-1||start_n!=s_arr.length){ len = 0; while(n<s_arr.length&&m<f_arr.length){ if(f_arr[m] == s_arr[n]){ len++; if(len>max_len){ max_len = len; max_n = n; max_m = m; } }else{ len = 0; } m++; n++; } if(start_m>0){ m = --start_m; n = start_n; }else if(start_n<s_arr.length-1){ m = start_m; n = ++start_n; }else if(start_m==0&&start_n==s_arr.length-1){ break; } } for(int count1 = max_len;count1>0;count1--){ System.out.print(f_arr[max_m-count1+1]); } if(max_len==0){ System.out.print(""+-1); } } }
这篇关于牛客网:最长公共子串问题的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南