动态规划算法-蒲公英云

动态规划算法

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); }