这道题我觉得,直接二重循环,记录最大长度和相应的字符就可以。
答案思路
这里的动态规划表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); } } }