1. 问题
求两个字符串的最大公共子序列
2. 解析
我们思考一下其实，是个很简单的问题,dp[i][j]//i表示a串到下标i,j表示b串到下标j,dp[i][j]表示当前最大公共子序列
则当a[i]=b[j]时 dp[i][j]=dp[i-1][j-1]+1;
否则dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
3. 设计
1 for (int i = 1; i <= m; i++){ 2 for (int j = 1; j <= n; j++){ 3 if (x[i - 1] == y[j - 1]){ 4 c[i][j] = c[i - 1][j - 1] + 1; 5 b[i][j] = 'a'; 6 } 7 else if (c[i - 1][j] >= c[i][j - 1]){ 8 c[i][j] = c[i - 1][j]; 9 b[i][j] = 'b'; 10 } 11 else{ 12 c[i][j] = c[i][j - 1]; 13 b[i][j] = 'c'; 14 } 15 } 16 }
4. 分析
m是a串长，n是b串长
O(m*n)
5. 源码
https://github.com/Tinkerllt/algorithm-work.git
1 #include<stdio.h> 2 #include<stdio.h> 3 #include<iostream> 4 #include<cmath> 5 #include<cstring> 6 #include<algorithm> 7 #include<bitset> 8 #include<set> 9 #include<deque> 10 #include<queue> 11 #include<vector> 12 //#include<unordered_map> 13 #include<map> 14 #include<stack> 15 using namespace std; 16 #define ll long long 17 #define ull unsigned long long 18 #define pii pair<int,int> 19 #define Pii pair<ll,int> 20 #define m_p make_pair 21 #define l_b lower_bound 22 #define u_b upper_bound 23 const int inf = 0x3f3f3f3f; 24 const ll linf = 0x3f3f3f3f3f3f3f3f; 25 const int maxn = 3e5 + 11; 26 const int maxm = 600 + 11; 27 const int mod = 1e9 + 7; 28 const double eps = 1e-5; 29 inline ll rd() { ll x = 0, f = 1; char ch = getchar(); while (ch<'0' || ch>'9') { if (ch == '-')f = -1; ch = getchar(); }while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }return x * f; } 30 inline ll qpow(ll a, ll b, ll p) { ll res = 1; while (b) { if (b & 1) { res *= a; res %= p; }b >>= 1; a = a * a%p; }return res; } 31 inline ll gcd(ll a, ll b) { if (b == 0) return a; return gcd(b, a%b); } 32 //iterator 33 //head 34 //priority_queue 35 int c[maxm][maxm]; 36 char b[maxm][maxm]; 37 void lcs(string x, string y){ 38 int m = x.length(); 39 int n = y.length(); 40 for (int i = 1; i <= m; i++) 41 c[i][0] = 0; 42 for (int j = 0; j <= n; j++) 43 c[0][j] = 0; 44 for (int i = 1; i <= m; i++){ 45 for (int j = 1; j <= n; j++){ 46 if (x[i - 1] == y[j - 1]){ 47 c[i][j] = c[i - 1][j - 1] + 1; 48 b[i][j] = 'a'; 49 } 50 else if (c[i - 1][j] >= c[i][j - 1]){ 51 c[i][j] = c[i - 1][j]; 52 b[i][j] = 'b'; 53 } 54 else{ 55 c[i][j] = c[i][j - 1]; 56 b[i][j] = 'c'; 57 } 58 } 59 } 60 } 61 62 void print_lcs(string x,int m, int n) 63 { 64 if (m == 0 || n == 0) 65 return; 66 if (b[m][n] == 'a'){ 67 print_lcs(x,m - 1, n - 1); 68 cout << x[m-1]; 69 } 70 else if (b[m][n] == 'b'){ 71 print_lcs(x, m - 1, n); 72 } 73 else 74 print_lcs(x, m, n - 1); 75 } 76 int main() 77 { 78 string x, y; 79 cin >> x >> y; 80 lcs(x, y); 81 print_lcs(x,x.length(), y.length()); 82 }