这题是经典的动态规划算法，有些帖子没说清楚，然后看了下wikipedia，基本上一张图能看懂递推关系，
基于这张图的直觉，自己写了一版：
import java.util.Arrays; public class CommonSubstring { public static String commonSub(String st1, String st2){ int index1 = 0; int index2 = 0; int maxLength = -1; if(st1==null || st2 == null){ return null; } int[][] cache = new int[st1.length()][st2.length()]; for(int[] row: cache){ Arrays.fill(row, -1); } //initialize boarder for(int i=0; i<st2.length();i++){ if(st1.charAt(0)==st2.charAt(i)){ cache[0][i] = (st1.charAt(0)==st2.charAt(i)?1:0); } } for(int i=1; i<st1.length();i++){ if(st2.charAt(0)==st1.charAt(i)){ cache[i][0] = (st2.charAt(0)==st1.charAt(i)?1:0); } } for(int i = 0 ; i < st1.length(); i++){ for(int j = 0 ; j < st2.length(); j++){ int length = calcLength(st1, st2, i, j, cache); if(length>maxLength){ maxLength = length; index1 = i; index2 = j; } } } return st1.substring(index1-maxLength+1, index1+1); } public static int calcLength(String st1, String st2, int i, int j, int[][] cache){ if(cache[i][j]!=-1){ return cache[i][j]; }else{ return cache[i][j]=(st1.charAt(i)==st2.charAt(j)?calcLength(st1, st2, i-1, j-1, cache)+1:0); } } public static void main(String[] str){ String str1 = "abdwhatthefuckdsgsd"; String str2 = "634whatthefuck8gsg"; System.out.println(commonSub(str1, str2)); } }