题解 | #公共子串计算#
公共子串计算
https://www.nowcoder.com/practice/98dc82c094e043ccb7e0570e5342dd1b
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) { BufferedReader r = new BufferedReader(new InputStreamReader(System.in)); String a, b; try { a = r.readLine(); b = r.readLine(); } catch (IOException e) { throw new RuntimeException(e); } char[] chs1 = a.toCharArray(); char[] chs2 = b.toCharArray(); char[] tmp; int le1 = chs1.length, le2 = chs2.length, i; if (le1 > le2) {//保证小串在前 i = le1; le1 = le2; le2 = i; tmp = chs1; chs1 = chs2; chs2 = tmp; } i = longestSubstr(chs1, chs2, le1 + 1, le2 + 1); System.out.print(i); } //常规动态规划求解 protected static int longestSubstr(char[] chs1, char[] chs2, int m, int n) { int[][] dp = new int[m][n]; int i = 1, j, max = 0; while (i < m) { j = 1; while (j < n) { if (chs1[i - 1] == chs2[j - 1]) { dp[i][j] = 1 + dp[i - 1][j - 1]; max = dp[i][j] > max ? dp[i][j] : max; } j++; } i++; } return max; } }