360网站名片怎么做,前端seo搜索引擎优化,ui设计定义,东莞清溪镇做网站公司求两个字符串的公共子序列我们都知道需要使用用动态规划思想
用res[i][j]表示截止到字符串A的第i个字符串和截止到字符串B的第j个字符的最长公共子序列。如两个字符串helloworld和loop#xff0c;res[5][3]表示子串hello和子串loo的最长公共子序列#xff0c;为lo#xff0…求两个字符串的公共子序列我们都知道需要使用用动态规划思想
用res[i][j]表示截止到字符串A的第i个字符串和截止到字符串B的第j个字符的最长公共子序列。如两个字符串helloworld和loopres[5][3]表示子串hello和子串loo的最长公共子序列为lo长度为2
状态转移方程
当i0或j0时res[i][j]0
当A[i]B[j]时res[i][j] res[i-1][j-1]1
当A[i]≠B[j]时res[i][j] max(res[i][j-1], res[i-1][j])
但是这样只能算出来最长公共子序列的长度如果需要输出子序列的话需要用回溯的方法比较难。我们可以用一个三维字符型数组来做动态规划数组这样既能得到实际的公共子序列也能得到长度
定义变量
char s1[105];
char s2[105];
char dp[105][105][105]; // 使用三维dp数组具体实现
scanf(%s %s,s1,s2);
int i,j;
int nstrlen(s1);
int mstrlen(s2);
dp[0][0][0] \0; // 初始化为空字符串for(i1;in;i){for(j1;jm;j){if(s1[i-1]s2[j-1]){strcpy(dp[i][j], dp[i-1][j-1]);int len strlen(dp[i][j]);dp[i][j][len]s1[i-1];dp[i][j][len1]\0;}else{int L1strlen(dp[i-1][j]);int L2strlen(dp[i][j-1]);if(L1L2)strcpy(dp[i][j], dp[i-1][j]);elsestrcpy(dp[i][j], dp[i][j-1]);}}
}
printf(%d\n,len(dp[n][m])); //输出子序列的最大长度
printf(%s\n, dp[n][m]); //输出最大子序列
