转载自: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;
}
}
}
分享到:
相关推荐
43<br><br>0061 树的实现 44<br><br>3.2 排序 48<br><br>0062 如何实现选择排序算法 48<br><br>0063 如何实现冒泡排序算法 49<br><br>0064 如何实现快速排序算法 50<br><br>0065 如何实现插入排序算法 ...
用动态规划求最大匹配子串,算法思想以及算法实现。还有时间复杂度分析。
1,01.zip<br>Toolbar - Custom status messages and tooltips<br>用户状态信息与工具提示(3KB)<END><br>2,02.zip<br>Remove system menu from floating toolbar<br>从浮动工具条中去除系统菜单(2KB)<END><br>3,03....
字符串函数 <br>长度与分析用 <br>datalength(Char_expr) 返回字符串包含字符数,但不包含后面的空格 <br>substring(expression,start,length) 不多说了,取子串 <br>right(char_expr,int_expr) 返回字符串右边int_...
<br>4、用邻接矩阵或邻接图实现一个有向图的存储,并实现单源最短路径算法的实现(这个类的一个成员函数),并能输出该图的关键路径。<br>注:1、要用面向对象的方法设计代码;<br>2、一个图是一个类的实例;<br>3、类...
<br><br>对于字符串拷贝来说,用上述三个函数都可以实现,但是其实现的效率和使用的方便程度不同:<br>• strcpy 无疑是最合适的选择:效率高且调用方便。<br>• snprintf 要额外指定格式符并且进行格式转化,麻烦且...
c++编写的串的基本操作。(全) cout<<"0-遍历"; cout<<" 1-初始化"; cout<<" 2-串赋值"; cout<<" 3-判串相等"<<endl; cout<<"4-求串长";...cout<<" 7-子串定位"<<endl; cout<<" 8-插入子串"; cout<<" 9-删除子串";
最大公共子串问题是IT行业的经典面试题之一,在生物信息等领域也有重要应用。该资源使用动态规划实现了最大公共子串查找算法,问题具体描述在Problem里,代码为code.py,调试结果请参考Readme。
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS
求一个数组的最大连续子串,和最大的串即为最大连续子串,其中还包括了最大连续子矩阵
java练习题,快来试试你的java水平吧!
fasta算法,Smith-waterman算法,编辑距离算法,最长公共子串算法
用<script></script>标签包围,这里面的代码如同java里面的代码一样有操作性 这里面的数据是弱数据类型 有顺序结构、循环结构、条件结构 还可以写函数,外还可以写拼接,点击按钮给表格加一行 BOM和DOM内置元素 ...
主要为大家详细介绍了python实现对求解最长回文子串的动态规划算法,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
华为od算法题,100分题-最多提取子串数目-Java解法
正则表达式教程<br> 正则表达式(regular expression)描述了一种字符串匹配的模式,可以用来检查一个串是否含有某种子串、将匹配的子串做替换或者从某个串中取出符合某个条件的子串等。<br><br>列目录时, dir *....
从键盘输入主串s以及子串t1和t2。编写程序,将主串s中所有t1子串替换为t2子串,输出替换后得到的串以及t1被替换的次数。要求子串查找采用改进KMP算法。 实验目的:掌握KMP算法。
最长公共子串匹配动态规划算法实现,源代码加注释,可运行啊,这描述限定真死板,还20 字符,吃多了啊
<mfrac> <mn> 1 </ mn> <mn> 2 </ mn> </ mfrac> </ math> $$ \ frac {1} {2} $$ -BPS通告和<math> <mfrac> <mn> 1 </ mn> <mn> 6 </ mn> </ mfrac> </ math> $$ \ frac {1} {6} $$ -BBS通过研究...
编程求出子串(模式串)的next值,利用kmp算法实现子串与多个主串的匹配,针对同一子串next值只计算一次。