题目描述
计算两个字符串的最大公共字串的长度，字符不区分大小写
最大公共子串与最长公共子序列不同
str1 = “12345” str2 = “123abc45”
最长公共子串子串：123 最长公共子序列：12345
这两个都可以用动态规划，只是状态转移方程有区别
首先两者都要创建一个二维数组dp[m][n]，并且初始化二维数组的内容为0： 然后，i 和j 分别从1开始，i++，j++循环： 如果str1[i-1] == str2[j-1]，则dp[i][j] = dp[i-1][j-1] + 1； 如果str1[i-1] != str2[j-1]，则 dp[i][j] = 0（最长公共子串） dp[i][j] = max(dp[i-1][j], dp[i][j-1])（最长公共子序列）
Java 代码如下：
import java.util.Scanner; public class Main { public static int getCommonStrLength(String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); int[][] arr = new int[len1+1][len2+1]; char[] c1 = s1.toCharArray(); char[] c2 = s2.toCharArray(); for(int i = 0; i < len1; i++) { arr[i][0] = 0; } for(int i = 0; i < len2; i++) { arr[0][i] = 0; } int max = 0; for(int i = 1; i < len1 + 1; i++) { for(int j = 1; j < len2 + 1; j++) { if(c1[i-1] == c2[j-1]) { arr[i][j] = arr[i-1][j-1] + 1; max = Math.max(max, arr[i][j]); }else { // arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j]); // 最长公共子序列 arr[i][j] = 0; // 最长公共子串 } } } // return arr[len1][len2]; // 最长公共子序列 return max; // 最长公共子串 } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()) { String line1 = sc.nextLine(); String line2 = sc.nextLine(); int result = getCommonStrLength(line1, line2); System.out.println(result); } sc.close(); } }测试结果如下，输入两个字符串 “asdfas” 和 “werasdfaswer”：
得到最长公共子串的长度是6（”asdfas”）
附：最长公共子序列原理图
