努力,成长,提高

在追求中进步
数据加载中……
用动态规划算法对最大子串问题的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用来存储已经计算过的字符串,用空间换时间。代码当然还可以优化,您也可以一试身手哦。

posted on 2009-09-15 01:19 孔阳 阅读(4391) 评论(7)  编辑  收藏

评论

# re: 用动态规划算法对最大子串问题的java实现 2009-09-15 14:35 mui

不知道这是不是个bug:
String str1 = "asdfxfghj";
String str2 = "fghjxasdf";
输出asdf。
  回复  更多评论    

# re: 用动态规划算法对最大子串问题的java实现[未登录] 2009-09-15 14:40 孔阳

@mui
是这个问题的
现在这个程序可能不会找到所有的同样等长的最长字符串
你这个返回的应该是asdf fghj
这个只需要稍微修改一下程序即可
如果字符串和当前最长的等长的话那么就添加到一个全局的list当中
实现方法多种多样:D
  回复  更多评论    

# re: 用动态规划算法对最大子串问题的java实现 2009-09-15 17:43 找个美女做老婆

Java乐园交流社区(四) 欢迎广大Javaer加入,大家一起交流,共同进步:
群号:81107233

Java乐园学习网站:http://www.javaly.cn
有大量的学习资料,视频教程。
  回复  更多评论    

# re: 用动态规划算法对最大子串问题的java实现 2009-09-16 14:27 lexy

算法有问题。
String str1 = "abcde1234567abcdefghijk";
String str2 = "abcdefgh12345";
返回:12345
应该返回:abcdefgh 吧?
  回复  更多评论    

# re: 用动态规划算法对最大子串问题的java实现 2009-09-16 17:04 孔阳

@lexy
感谢lexy的提醒,现在代码已经更新,原因在原文里面有说明:D
  回复  更多评论    

# re: 用动态规划算法对最大子串问题的java实现 2009-11-04 21:11 ddr

在不考虑性能的情况下 ,看看我这段代码能不能完成这个需求
public String findMaxSubString(String str,String tarStr){
String temp = "";
if(str.length()>tarStr.length()){
temp = str;
str = tarStr;
tarStr = temp;
}
temp = str;
int strLength = str.length();
for( ;strLength>0;strLength--){
String temp_ =null;
while(true){
temp_ = str.substring(0,strLength);
str = str.substring(1);
if(tarStr.indexOf(temp_)>0)
return temp_;
if(str.length()<strLength){
str = temp;
break;
}
}
}
return null;
}
  回复  更多评论    

# re: 用动态规划算法对最大子串问题的java实现 2011-12-07 15:02 flounders

@ddr
你的方式能很好的实现功能,不过性能太差了。。
  回复  更多评论    

只有注册用户登录后才能发表评论。


网站导航: