动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法
动态规划求解最长公共子串问题
算法思想
求字符串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)
按照上面这个公式，我们用容易写出这个算法的实现
算法实现
1 int commstr(char *str1, char *str2)
2 /* 返回str1,str2的最长公共之串长度*/
3 {
4 int len1=strlen(str1),len2=strlen(str2),row,col,max=0;
5 int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间
6 for (row=0; row
7 pf[row] = new int[len2+1];
8
9 //数组赋初值
10 for (row=0; row
11 pf[row][0] = 0;
12 for (col=0; col
13 pf[0][col] = 0;
14
15 for (row=1; row<=len1; row++)
16 for (col=1;col<=len2; col++)
17 {
18 if (str1[row-1] == str2[col-1])
19 {
20 pf[row][col] = pf[row-1][col-1] + 1;
21 max = pf[row][col] > max ? pf[row][col] : max;
22 }
23 else
24 pf[row][col] = 0;
25 }
26 //空间回收
27 for (row=0; row
28 delete[] pf[row];
29 delete[] pf;
30
31 return max;
32 }
程序的输出
字符串"blog.csdn.net"和"csdn.blog"求公共子串时的输出结果
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
max substr length:5
这是程序的输出结果,请注意红色字体
时间空间复杂度分析
如果用n,m表示两个字符串的长度的话，那么算法的
时间复杂度为O(n*m),空间复杂度也为O(n*m)
附：完整的源程序g++编译通过
#include
#include
void print_table(char *str1,char *str2,int **pf)
{
int i,j,row,col;
row = strlen(str1);
col = strlen(str2);
printf("\t\t");
for (i=0; i
printf("%c\t",str2[i]);
for (i=0; i<=row; i++)
{
for (j=0; j<=col; j++)
{
if (j == 0)
{
printf("\n");
if (i)
printf("%c\t",str1[i-1]);
else
printf("\t");
}
printf("%d\t",pf[i][j]);
}
}
}
int commstr(char *str1, char *str2)
/* 返回str1,str2的最长公共之串长度*/
{
int len1=strlen(str1),len2=strlen(str2),row,col,max=0;
int **pf = new int*[len1+1];//动态分配一个二维数组作为辅助空间
for (row=0; row
pf[row] = new int[len2+1];
//数组赋初值
for (row=0; row
pf[row][0] = 0;
for (col=0; col
pf[0][col] = 0;
for (row=1; row<=len1; row++)
for (col=1;col<=len2; col++)
{
if (str1[row-1] == str2[col-1])
{
pf[row][col] = pf[row-1][col-1] + 1;
max = pf[row][col] > max ? pf[row][col] : max;
}
else
pf[row][col] = 0;
}
print_table(str1,str2,pf);
//空间回收
for (row=0; row
delete[] pf[row];
delete[] pf;
return max;
}
int main(int argc,char **argv)
{
if (argc >= 3)
{
printf("String:\n\t1. %s\n\t2. %s\n",argv[1],argv[2]);
printf("\nmax substr length:%d\n",commstr(argv[1],argv[2]));
}
return 0;
}
