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

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!