用动态策划算法对最大子串问题的java实现[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用来存储已经计算过的字符串,用空间换时间.代码当然还可以优化,您也可以一试身手哦.