<转载>--用动态规划算法对最大子串问题的java实现

转载自:http://www.blogjava.net/heack/archive/2009/09/15/295080.html

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;
                }
        }
 
}