求兩個字符串的公共子序列

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;}

總結

以上是生活随笔為你收集整理的求最长公共子序列长度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。