1.最长公共子串：
转自：http://www.yuanma.org/data/2006/0723/article_1215.htm
算法思想
求字符串str1,str2的最长公共子串的长度。
定义二元函数函数f(m,n)：分别以str1[m],str2[n]结尾的连续公共子串的长度
而对于f(m+1,n+1) 有以下两种情况
1.str1[m+1] != str2[n+1],则有f(m+1,n+1) =0
2.str1[m+1] == str2[n+1],则有f(m+1,n+1) = f(m,n) + 1
另外f(0,j) = 0(j>=0)
f(j,0) = 0 (j>=0)
输出结果：
String:
1. blog.csdn.net
2. csdn.blog
c
s
d
n
.
b
l
o
g
0
0
0
0
0
0
0
0
0
0
b
0
0
0
0
0
0
1
0
0
0
l
0
0
0
0
0
0
0
2
0
0
o
0
0
0
0
0
0
0
0
3
0
g
0
0
0
0
0
0
0
0
0
4
.
0
0
0
0
0
1
0
0
0
0
c
0
1
0
0
0
0
0
0
0
0
s
0
0
2
0
0
0
0
0
0
0
d
0
0
0
3
0
0
0
0
0
0
n
0
0
0
0
4
0
0
0
0
0
.
0
0
0
0
0
5
0
0
0
0
n
0
0
0
0
1
0
0
0
0
0
e
0
0
0
0
0
0
0
0
0
0
t
0
0
0
0
0
0
0
0
0
0
Java实现：
public static String getValue(String str1,String str2){
int maxi = 0;
int max = 0;
int[][] f = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str2.length();i++ ){
f[0][i] = 0;
}
for(int i=0;i<=str1.length();i++){
f[i][0] = 0;
}
for(int i=0;i<str1.length();i++){
for(int j=0;j<str2.length();j++){
if(str1.charAt(i)==str2.charAt(j)){
f[i+1][j+1] = f[i][j] + 1;
if(max<f[i+1][j+1]){
max = f[i+1][j+1];
maxi = i+1;
}
}else{
f[i+1][j+1] = 0;
}
}
}
return str1.substring(maxi-max,maxi);
}
2.
分享到：
相关推荐
"动态规划算法的应用" 动态规划算法是一种非常强大且广泛应用的算法思想，它可以解决许多复杂的问题。动态规划算法的核心思想是将问题分解成小问题，然后使用Memoization技术将中间结果存储起来，以便后续问题的...
动态规划算法经典题目分析 动态规划是一种非常经典的算法思想，解决的问题领域非常广泛。动态规划的基本思想是将一个复杂的问题分解成多个小问题，通过解决这些小问题来解决整个问题。今天，我们将要探讨动态规划的...
动态规划算法课件PPT 动态规划算法是解决问题的有效方法，它将问题分解成多个子问题，然后通过解决这些子问题来解决原问题。动态规划算法与分治法类似，但不同的是，动态规划算法中子问题之间存在相互依赖关系，...
动态规划算法是一种强大的工具，主要用于解决多阶段决策过程中的最优化问题。在计算机科学和算法设计中，动态规划提供了一种系统化的方法来处理复杂问题，尤其在那些问题的最优解可以通过组合子问题的最优解来得出的...
北京工业大学--算法作业2--动态规划算法实现0-1背包问题---Java代码 利用动态规划算法实现0-1背包问题或装配线调度问题。（二选一） 要求测试数据以文本文件的形式存储， 即所有的数据由文本文件读入。 利用动态...
"动态规划算法实现投资问题" 资源分配问题是指在给定的总资源下，如何将其分配给多个工程项目，以获得最大利润的问题。这种问题可以使用动态规划算法来解决。 在动态规划算法中，我们首先需要定义状态变量，例如...