动态规划求解最长公共子串问题

《动态规划求解最长公共子串问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划求解最长公共子串问题今夜偏知春气暖，虫声新透绿窗纱。溪云初起日沉阁，山雨欲来风满楼。既来之，则安之。风流不在谈锋胜，袖手无言味最长。白也诗无敌，飘然思不群。动态规划求解最长公共子串问题算法思想求字符串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)=02.str1[m+1]==str2[n+1],则有f(m+1,n+1)=f(m,n)+1另外f(0,j)=0(j

2、>=0)f(j,0)=0(j>=0)按照上面这个公式，我们用容易写出这个算法的实现算法实现1intcommstr(char*str1,char*str2)2/*返回str1,str2的最长公共之串长度*/3{4intlen1=strlen(str1),len2=strlen(str2),row,col,max=0;5int**pf=newint*[len1+1];//动态分配一个二维数组作为辅助空间6for(row=0;row

3、+1;row++)11pf[row][0]=0;12for(col=0;colmax?pf[row][col]:max;22}23else24pf[row][col]=0;25}26//空间回收27for(row

4、=0;row

5、00000e0000000000t0000000000maxsubstrlength:5这是程序的输出结果,请注意红色字体时间空间复杂度分析如果用n,m表示两个字符串的长度的话，那么算法的时间复杂度为O(n*m),空间复杂度也为O(n*m)附：完整的源程序g++编译通过#include#includevoidprint_table(char*str1,char*str2,int**pf){inti,j,row,col;row=strlen(str1);col=strlen(str2);printf("tt");for

6、(i=0;i

7、0;int**pf=newint*[len1+1];//动态分配一个二维数组作为辅助空间for(row=0;row

8、-1][col-1]+1;max=pf[row][c