數據結構與演算法：兩個字元串的最長公共子串

獲取兩個字元串的最長公共子串

基本思路是：

獲取兩個字元串中長的那個，記為max

獲取兩個字元串中短的那個，記為min

依次遍歷min的子串，從最長開始，依次減少。

可以看到 j 和 k是同時增加的。所以是依據截取固定長度來定的。

public class MaxSubstring { //獲取兩個字元串中最大相同子串。 /** * 思路：1、將短的那個子串按照長度遞減的方式獲取到。 * 2、用長串去判斷是否包含每次獲取到的子串，若包含則就找到最大相同子串 * @param s1 * @param s2 * @return max substring */ public static String getMaxsubstring(String s1,String s2) { String max="",min=""; max=(s1.length()>s2.length())?s1:s2; min=(max==s1)?s2:s1; for(int i=0;i<min.length();i++) { for(int j=0,k=min.length()-i;k!=min.length()+1;j++,k++) { String temp=min.substring(j,k); //System.out.println("temp--:"+temp); if(max.contains(temp)) return temp; } } return ""; } /** * @param args */ public static void main(String[] args) { String xx="abcdefghij",yy="34cdefgff"; String dd=MaxSubstring.getMaxsubstring(xx,yy); System.out.println(dd); } }

推薦閱讀：