最大公共子串長度問題就是：

求兩個串的所有子串中能夠匹配上的最大長度是多少。

比如：“abcdkkk” 和 “baabcdadabc”，
可以找到的最長的公共子串是"abcd",所以最大公共子串長度為4。

下面的程序是采用矩陣法進行求解的，這對串的規模不大的情況還是比較有效的解法。

請分析該解法的思路，并補全劃線部分缺失的代碼。

這個有點dp的意思，分別計算兩個字符串每一個字符到另一個字符是否相等 若相等 則加前面字符的最大字符串 若前面字符也分別相等則他就等于a[i-1][j-1]+1 若不想等則為0+1

?測試數據1：

abcdkkk baabcdadabc

?

---

import java.util.Scanner;public class Main {static Scanner sc =new Scanner(System.in);static int f(String s1, String s2) {char[] c1 = s1.toCharArray();char[] c2 = s2.toCharArray();int[][] a = new int[c1.length + 1][c2.length + 1];int max = 0;for (int i = 1; i < a.length; i++) {for (int j = 1; j < a[i].length; j++) {if (c1[i - 1] == c2[j - 1]) {a[i][j] = a[i - 1][j - 1] + 1; //填空處if (a[i][j] > max)max = a[i][j];}}}return max;}public static void main(String[] args) {int n = f(sc.next(), sc.next());System.out.println(n);} }

---

總結

以上是生活随笔為你收集整理的Java最大公共子串（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。