Go语言视频零基础入门到精通

五菱

最大字串问题描述大概就是给定2个字符串，找出他们两个共有的最长子字符串。比如一个是"tabcfg"另外一个"abckj"那么最大子串就是"abc".
    动态规划算法最重要的就是分解问题，找出递归。说一下我的思考思路，首先拿到2个字符串，如何找到最长子串呢？
1.假设他们(字符串a,b)的头字母不相同的话，那么分别去掉首字母比较，也就是说用a.subString(1)和b比较，用b.subString(1)和a比较，最长子字符串没变吧？答案是肯定的。ok递归出现了，结束条件就是有一个字符串变空，返回值就是a和b的最长子串。

2.假设他们头字母相同，那么一直比较下去，直到两者的第n个字母不相同，然后把前n-1个字母存为子字符串c,把a.subString(1)和b的比较结果记为d,b.subString(1)和a比较结果记为e,那么返回c，d和e最长的一个

程序运行结果：
c:\java\java CompareStr
最大字串有:
5246
fghj
asdf
[pre]import java.util.HashMap;import java.util.Map; /*** @author HEACK**/public class CompareStr {   public static void main(String[] args) {                       String str1 = "asdfxfghj5246";         String str2 = "fghjxasdf6743575246";         CompareStr cj = new CompareStr();        String longestStr=cj.getLongestString(str1,str2);        System.out.println("最长子串有：\n\r"+longestStr);         int n=longestStr.length();                str1=str1.replaceAll(longestStr, "_");         str2=str2.replaceAll(longestStr,"_");        longestStr=cj.getLongestString(str1,str2);                   int m=longestStr.length();         while(m==n){             System.out.println(longestStr);             str1=str1.replaceAll(longestStr, "_");             str2=str2.replaceAll(longestStr,"_");             longestStr=cj.getLongestString(str1,str2);              m=longestStr.length();        }   }    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 == str2List) {             longestStr.append(str1List);          } 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;      } } }[/pre]