题解 | #查找两个字符串a,b中的最长公共子串#
此题是最长子串,子串,子串。可以用动态规划,可以用双指针。
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str1 = sc.nextLine(); String str2 = sc.nextLine(); if (str1.length() >= str2.length()) { helper(str2, str1); // doublePointer(str2, str1); } else { helper(str1,str2); // doublePointer(str1, str2); } } /** * 动态规划,dp[i][j]表示子串str1[1...i]中以i结尾的子串 和 子串str2[1...j]中以j结尾的子串 之间的最长公共子串 * 当str1[i] == str2[j]时,dp[i][j] = dp[i-1][j-1]+1; * 否则,dp[i][j] = 0; * 注意:此题是最长公共子串,不是子序列 */ public static void helper(String str1, String str2) { // str1是短字符串,str2是长字符串 int l1 = str1.length(), l2 = str2.length(); int[][] dp = new int[l1+1][l2+1]; int max = 0; // 最长字串长度 int index = 0; // 生成最长子串时的短字符串子串的结尾位置 for (int i = 1; i <= l1; i++) { for (int j = 1; j <= l2; j++) { if (str1.charAt(i-1) == str2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1] + 1; if (dp[i][j] > max) { max = dp[i][j]; index = i; } } } } System.out.println(str1.substring(index - max, index)); } public static void doublePointer(String str1, String str2) { // str1是短字符串,str2是长字符串 String result = ""; int left = 0; // 左指针 int right = left + 1; // 右指针 while (right <= str1.length()) { String tmp = str1.substring(left, right); if (str2.contains(tmp)) { if (result.length() < tmp.length()) { result = tmp; } right++; // 是子串的情况下,只移动右指针 } else { // 左指针移动一位 left++; right = left + 1; } } System.out.println(result); } }