用动态规划算法对最大子串问题的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;
　　　　　　　　　　　　　　　　}
　　　　　　　　}
　
}