用動態規劃算法對最大子串問題的java實現

最大字串問題描述大概就是給定2個字符串，找出他們兩個共有的最長字符串。比如一個是"tabcfg"另外一個"abckj"那麼最大子串就是"abc".

動態規劃算法最重要的就是分解問題，找出遞歸。說一下我的思考思路，首先拿到2個字符串，如何找到最長子串呢？

1.假設他們(字符串a,b)的頭字母不相同的話，那麼分別去掉首字母比較，也就是說用a.subString(1)和b比較，用 b.subString(1)和a比較，最長子字符串沒變吧？答案是肯定的。ok遞歸出現了，結束條件就是有一個字符串變空，返回值就是a和b的最長子串。

b.假設他們頭字母相同，那麼一直比較下去，知道兩者的第n個字母不相同，然後把前n-1個字母存為子字符串c,把a.subString(1)和b返回結果記為d,b.subString(1)和a返回結果記為e,那麼返回c，d和e最長的一個(感謝lexy的評論，之前確實遺漏一種情況。不應該直接把前面的相同的去掉直接比較的，現在代碼已經更新了)。

也許有人說應該從後面往前面比較，找到相同的然後一個個再往前比，其實道理都是一樣的，關鍵要找到分解問題的方法。這裡只是拋磚引玉，下面是具體的java實現。

import　java.util.HashMap;
import　java.util.Map;

/**
*　@author　HEACK
*
*/
public　class　CompareStr　{

　　　　　　　　 /**
　　　　　　　　 *　@param　args
　　　　　　　　 */
　　　　　　　　 public　static　void　main(String[]　args)　{
　　　　　　　　　　　　　　　　 //　TODO　Auto-generated　method　stub
　　　　　　　　　　　　　　　　 String　str1　=　"abcde1234567abcdefghijk";
　　　　　　　　　　　　　　　　 String　str2　=　"abcdefgh12345";

　　　　　　　　　　　　　　　　 //String　str2　=　"abc　happyies　dutcbirthday　peter";
　　　　　　　　　　　　　　　　 CompareStr　cj　=　new　CompareStr();
　　　　　　　　　　　　　　　　 System.out.println(cj.getLongestString(str1,str2));

　　　　　　　　 }

　　　　　　　　 private　boolean　isEmpty(String　str)　{
　　　　　　　　　　　　　　　　 return　str　==　null　||　str.trim().length()　==　0;
　　　　　　　　 }
　　　　　　　　 private　Map　map　=　new　HashMap();

　　　　　　　　 private　String　getLongestString(String　str1,　String　str2)　{
　　　　　　　　　　　　　　　　 if　(isEmpty(str1)　||　isEmpty(str2))　{
　　　　　　　　　　　　　　　　　　　　　　　　 return　"";
　　　　　　　　　　　　　　　　 }
　　　　　　　　　　　　　　　　 StringBuffer　key　=　new　StringBuffer();
　　　　　　　　　　　　　　　　 key.append(str1).append("&&").append(str2);
　　　　　　　　　　　　　　　　 if　(map.containsKey(key.toString()))　{
　　　　　　　　　　　　　　　　　　　　　　　　 return　(String)map.get(key.toString());
　　　　　　　　　　　　　　　　 }
　　　　　　　　　　　　　　　　 StringBuffer　longestStr　=　new　StringBuffer();
　　　　　　　　　　　　　　　　 char[]　str1List　=　str1.toCharArray();
　　　　　　　　　　　　　　　　 char[]　str2List　=　str2.toCharArray();
　　　　　　　　　　　　　　　　 int　i　=　0;
　　　　　　　　　　　　　　　　 for　(i　=　0;　i　<　str1List.length　&&　i　<　str2List.length;　i++)　{
　　　　　　　　　　　　　　　　　　　　　　　　 if　(str1List[i]　==　str2List[i])　{
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 longestStr.append(str1List[i]);
　　　　　　　　　　　　　　　　　　　　　　　　 }　else　{
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 break;
　　　　　　　　　　　　　　　　　　　　　　　　 }
　　　　　　　　　　　　　　　　 }
　　　　　　　　　　　　　　　　 String　subStr1　=　str1.substring(i);
　　　　　　　　　　　　　　　　 String　subStr2　=　str2.substring(i);
　　　　　　　　　　　　　　　　 if　(i　==　0)　{
　　　　　　　　　　　　　　　　　　　　　　　　 String　retStr1　=　getLongestString(subStr1.substring(1),　subStr2);
　　　　　　　　　　　　　　　　　　　　　　　　 String　retStr2　=　getLongestString(subStr1,　subStr2.substring(1));
　　　　　　　　　　　　　　　　　　　　　　　　 String　returnStr　=　retStr1.length()　>=　retStr2.length()　?　retStr1　:　retStr2;
　　　　　　　　　　　　　　　　　　　　　　　　 map.put(key.toString(),　returnStr);
　　　　　　　　　　　　　　　　　　　　　　　　 return　returnStr;
　　　　　　　　　　　　　　　　 }　else　{
　　　　　　　　　　　　　　　　　　　　　　　　 String　retStr1　=　getLongestString(str1.substring(1),　str2);
　　　　　　　　　　　　　　　　　　　　　　　　 String　retStr2　=　getLongestString(str1,　str2.substring(1));
　　　　　　　　　　　　　　　　　　　　　　　　 String　retStr　=　retStr1.length()　>　retStr2.length()　?　retStr1
　　　　　　　　　　　　　　　　　　　　 :　retStr2;
　　　　　　　　　　　　　　　　　　　　　　　　 String　returnStr　=　retStr.length()　>=　longestStr.toString().length()　?　retStr
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 :　longestStr.toString();
　　　　　　　　　　　　　　　　　　　　　　　　 map.put(key.toString(),　returnStr);
　　　　　　　　　　　　　　　　　　　　　　　　 return　returnStr;
　　　　　　　　　　　　　　　　 }
　　　　　　　　 }

}

HashMap用來存儲已經計算過的字符串，用空間換時間。代碼當然還可以優化，您也可以一試身手哦。