题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 String a = null; String b = null; while (in.hasNextLine()) { // 注意 while 处理多个 case String curLine = in.nextLine(); if (a == null) { a = curLine; continue; } if (b == null) { b = curLine; } } System.out.println(commonLongSubStrUseDp(a, b)); } private static String commonLongSubStrUseDp(String a, String b) { if (a == null || b == null) { return ""; } // 此处交换位置,让a的字符串保持是最短的。 if (a.length() > b.length()) { return commonLongSubStrUseDp(b, a); } if (a.contains(b)) { return b; } int m = a.length() + 1; int n = b.length() + 1; // 动态规划 // dp[i][j]到a的第i个下标结尾,b的第j个下标结尾的是公共子串 // 如果到字符串a下标i的位置,到字符串b的j位置是公共子串,那么,到第i-1个,以及第j-1个位置也是公共子串 // 动态规划公式:dp[i][j] = dp[i-1][j-1]+1; int[][] dp = new int[m][n]; int maxLen = 0; int index = 0; for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { if (a.charAt(i - 1) == b.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1] + 1; if (dp[i][j] > maxLen) { maxLen = dp[i][j]; index = i; } } } } return a.substring(index - maxLen, index); } }