import java.util.*; public class Solution { /** * longest common substring * @param str1 string字符串 the string * @param str2 string字符串 the string * @return string字符串 */ public String LCS (String str1, String str2) { char[] arr1 = str1.toCharArray() ; char[] arr2 = str2.toCharArray() ; int len1 = arr1.length ; int len2 = arr2.length ; //f[i][j]表示以arr1[i] arr2[j]结尾的最长公共子串的长度 int f[][] = new int[len1][len2] ; int maxLen = 0 ; int t_i = 0 ;//记录最长的公共子串的最后一个字符在arr1中的位置 int t_j = 0 ;//记录最长的公共子串的最后一个字符在arr1中的位置 for(int i = 0 ; i < len1 ; i ++) { for(int j = 0 ; j < len2 ; j ++) { if(i == 0 || j == 0) { f[i][j] = arr1[i] == arr2[j] ? 1 : 0 ; } else { if(arr1[i] == arr2[j]) { f[i][j] = 1 ; if(arr1[i-1] == arr2[j-1]) { f[i][j] = Math.max(f[i][j] , f[i-1][j-1] + 1) ; } } } if(f[i][j] > maxLen) { maxLen = f[i][j] ; t_i = i ; t_j = j ; } } } int start = t_i - maxLen + 1 ; int end = t_i + 1 ; return str1.substring(start , end) ; } }