求最长公共子序列长度

求两个字符串的公共子序列

1.求最长公共子序列（子序列可以不连续）

这是一道动态规划题，设二维数组dp[i][j]，dp[i][j]表示a串前i个字符（包括第i个）与b串前j个字符（包括第j个）所有的公共子序列的最长长度。
例如，a串abbcd，b串abcd，dp[3][3]就表示的a的前三个字符与b的前三个字符的最长公共子序列长度，值为2。a串中的ab与b串中的ab一致，长度为2。
求dp数组的方法为：
dp[i][j] = 0 ， i == 0 || j == 0
dp[i][j] = dp[i-1][j-1] +1 ， a[i] = b[j]
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) ， a[i] !=b[j]

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main(){string a,b;cin>>a>>b;int alen = a.size();int blen = b.size();int dp[100][100];for(int i=0;i<alen+1;i++) dp[i][0]=0; //若i==0或j==0for(int j=0;j<alen+1;j++) dp[0][j]=0; //dp[i][j] = 0for(int i=1;i<alen+1;i++){for(int j=1;j<blen+1;j++){if(a[i-1]==b[j-1]){dp[i][j] = dp[i-1][j-1] +1;}else{dp[i][j] = max(dp[i][j-1],dp[i-1][j]);}cout<<dp[i][j]<<" "; //输出当前dp矩阵}}cout<< dp[alem][blen]; //dp[alem][blen]即为当前两个串的最长公共子序列长度 }

2.最长连续子串

求最长连续子串比不连续的简单了一些，只需删除上边代码里的else部分即可，这里的dp[i][j]可以理解为以a的第i个字符与b的第j个字符为结尾的最长公共子串的长度，由此可得a[i] != b[j]时，dp[i][j] = 0

#include<iostream> #include<cstdio> #include<cstring> using namespace std; int main(){string a,b;cin>>a>>b;int alen = a.size();int blen = b.size();int dp[100][100];int Max=0;for(int i=0;i<alen+1;i++) dp[i][0]=0;for(int j=0;j<alen+1;j++) dp[0][j]=0;for(int i=1;i<alen+1;i++){for(int j=1;j<blen+1;j++){if(a[i-1]==b[j-1]){dp[i][j] = dp[i-1][j-1] +1;}cout<<dp[i][j]<<" ";if(dp[i][j]>Max)Max = dp[i][j]; //保存数组里的最大值}cout<<endl;}cout<< Max;}

总结

以上是生活随笔为你收集整理的求最长公共子序列长度的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。