我要评论概要：
字符串动态规划问题——求解公共最长子串
一、问题描述
longest common substring
求解公共最长子串 ▶给定两个字符串a,b c是a,b的最长公共子串 ▶求解c的序列
此题用动态规划算法求解
二、问题分析
- 动态规划重点：定义状态转移方程
初始条件
边界条件
逆推过程
- 确定动态规划数组dp维度：本题使用二维dp[ ][ ]
- 注意：公共子串必须是连续的，公共子序列可以不连续，分清两者
三、问题求解
- 动态规划：定义状态转移方程
初始条件 dp[0][0]=0
边界条件 dp[ i ][0]=0
dp[0][ j ]=0
逆推过程 dp[ i ][ j ]=dp[i-1][j-1]+1
dp[ i ][ j ]=0
- 定义函数：
求解二维动态规划数组dp[][]
求解dp[][]最大值max，即公共子串最大长度
由dp构造subs，求解最长公共子序列
- 代码如下：
求解dp数组
//求解dp数组
void lcslength(string a,string b) {
dp=new int [m+1][n+1];
dp[0][0]=0;
for(int i=0;i<=m;i++)
dp[i][0]=0;
for(int j=0;j<=n;j++)
dp[0][j]=0;
for(int c=1;c<=m;c++) {
for(int d=1;d<=n;d++) {
if(a.charat(c-1)==b.charat(d-1))
dp[c][d]=dp[c-1][d-1]+1;
else
dp[c][d]=0;
}
}
}求解最长公共子序列
string getasubs(string a,string b,int max) {
string subs="";
for(int i=0;i<=m;i++) {
for(int j=0;j<=n;j++) {
if(max==dp[i][j]) {
for(int s=i-max+1;s<=i;s++) {
subs=subs+a.charat(s-1);
}
}
}
}
return subs;
}
发表评论