算法分析设计实践——最长公共子序列

1.问题

对于序列a和序列b，求其最长公共子序列

2.解析

通过动态规划的方式

dp[i][j] 前i个字符的x和前j个字符的y的最长公共子序列

当a[i] = b[j] 的时候

dp[i][j] = max(dp[i][j] , dp[i - 1][j - 1] + 1)

如果第i位和第j位相等的话，那么最长序列长度 + 1

当 a[i] != b[j] 的时候

dp[i][j] = max(dp[i][j] , dp[i - 1][j] , dp[i][j - 1])

如果第i位和第j不相等的话，那么最长公共子序列的长度则从 dp[i - 1][j] 和 dp[i][j - 1] 转移过来

3.设计

 1 void lcs()
 2 {
 3     for (int i = 0; i <= len1; ++i) dp[i][0] = 0;
 4     for (int i = 0; i <= len2; ++i) dp[0][i] = 0;
 5     for (int i = 1; i <= len1; ++i)
 6     {
 7         for (int j = 1; j <= len2; ++j)
 8         {
 9             if (arr[i] == brr[j])
10                 dp[i][j] = dp[i - 1][j - 1] + 1;
11             else
12             {
13                 if (dp[i - 1][j] > dp[i][j - 1])
14                 {
15                     res[i][j] = 1;
16                     dp[i][j] = dp[i - 1][j];
17                 }
18                 else
19                 {
20                     res[i][j] = 2;
21                     dp[i][j] = dp[i][j - 1];
22                 }
23             }
24         }
25     }
26 }
27 string getlcs()
28 {
29     int i = len1, j = len2;
30     string ans = "";
31     while (i > 0 && j > 0)
32     {
33         if (!res[i][j])
34         {
35             ans = arr[i] + ans;
36             i--, j--;
37         }
38         else if (res[i][j] == 1)
39         {
40             i--; 
41         }
42         else
43         {
44             j--;
45         }
46     }
47     return ans;
48 }

4.分析

时间复杂度：O(n * m)

5.源码

 1 #include<cstdio>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<iostream>
 6 #include<vector>
 7 #include<queue>
 8 #include<set>
 9 #include<stack>
10 #include<map>
11 #include<cctype>
12 #define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
13 #define mem(a,x) memset(a,x,sizeof(a))
14 #define lson rt<<1,l,mid
15 #define rson rt<<1|1,mid + 1,r
16 #define P pair<int,int>
17 #define ull unsigned long long
18 using namespace std;
19 typedef long long ll;
20 const int maxn = 2e5 + 10;
21 const ll mod = 998244353;
22 const int inf = 0x3f3f3f3f;
23 const long long INF = 0x3f3f3f3f3f3f3f3f;
24 const double eps = 1e-7;
25 
26 inline ll read()
27 {
28     ll X = 0, w = 0; char ch = 0;
29     while (!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }
30     while (isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();
31     return w ? -X : X;
32 }
33 
34 int len1, len2;
35 int dp[1000][1000];
36 string arr, brr;
37 int res[1000][1000];
38 void lcs()
39 {
40     for (int i = 0; i <= len1; ++i) dp[i][0] = 0;
41     for (int i = 0; i <= len2; ++i) dp[0][i] = 0;
42     for (int i = 1; i <= len1; ++i)
43     {
44         for (int j = 1; j <= len2; ++j)
45         {
46             if (arr[i] == brr[j])
47                 dp[i][j] = dp[i - 1][j - 1] + 1;
48             else
49             {
50                 if (dp[i - 1][j] > dp[i][j - 1])
51                 {
52                     res[i][j] = 1;
53                     dp[i][j] = dp[i - 1][j];
54                 }
55                 else
56                 {
57                     res[i][j] = 2;
58                     dp[i][j] = dp[i][j - 1];
59                 }
60             }
61         }
62     }
63 }
64 string getlcs()
65 {
66     int i = len1, j = len2;
67     string ans = "";
68     while (i > 0 && j > 0)
69     {
70         if (!res[i][j])
71         {
72             ans = arr[i] + ans;
73             i--, j--;
74         }
75         else if (res[i][j] == 1)
76         {
77             i--; 
78         }
79         else
80         {
81             j--;
82         }
83     }
84     return ans;
85 }
86 
87 int main()
88 {
89     cin >> arr >> brr;
90     len1 = arr.size(), len2 = brr.size();
91     arr = " " + arr;
92     brr = " " + brr;
93     lcs();
94     cout << "最长公共字串长度： " << dp[len1][len2] << endl;
95     cout << "最长公共字串： " << getlcs() << endl;
96     return 0;
97 }

完整代码

https://github.com/BambooCertain/Algorithm.git