题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
暴力 + 剪枝
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String a = in.nextLine();
String b = in.nextLine();
// a指向较短的
if (a.length() > b.length()) {
String temp = a;
a = b;
b = temp;
}
String maxSub = "";
// a.length() - i + 1 > maxSub.length() 剪枝 如果剩下的字符构成的子串已经小于最大子串的长度就没必要再判断了
for (int i = 0; i < a.length() && a.length() - i + 1 > maxSub.length(); i++) {
// 如果 substring(i, j) 是公共子串 那么substring(i, j - 1)也一定是公共子串 所以从右边开始遍历
for (int j = a.length(); j > i; j--) {
String sub = a.substring(i, j);
if (b.contains(sub)) {
maxSub = sub.length() > maxSub.length() ? sub : maxSub;
}
}
}
System.out.println(maxSub);
}
}
动态规划
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String a = in.nextLine();
String b = in.nextLine();
if (a.length() > b.length()) {
String temp = a;
a = b;
b = temp;
}
int m = a.length() + 1;
int n = b.length() + 1;
int max = Integer.MIN_VALUE;
int index = 0;
// dp[i][j] 存储 a[i]到b[j]之间最长公共子串的长度
int[][] dp = new int[m][n];
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;
index = dp[i][j] > max ? i : index;
max = Math.max(dp[i][j], max);
}
}
}
System.out.println(a.substring(index - max, index));
}
}
