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

2021-02-03 22:17

阅读：742

标签：EDA ++i gif fine 算法时间 math ide dash

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

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 0] = 0;
 4     for (int i = 0; i 0][i] = 0;
 5     for (int i = 1; i i)
 6     {
 7         for (int j = 1; j 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 2 #includestring.h>
 3 #include
 4 #include 5 #include 6 #include 7 #include 8 #includeset>
 9 #include10 #include11 #include12 #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 rt15 #define rson rt16 #define P pair17 #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 0] = 0;
41     for (int i = 0; i 0][i] = 0;
42     for (int i = 1; i i)
43     {
44         for (int j = 1; j 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 "最长公共字串长度： "  endl;
95     cout "最长公共字串： "  endl;
96     return 0;
97 }

完整代码

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

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

标签：EDA ++i gif fine 算法时间 math ide dash

原文地址：https://www.cnblogs.com/DreamACMer/p/12799216.html

上一篇：JavaScript连载7-一元运算符、赋值运算符、逻辑运算符

下一篇：初识 java

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：算法分析设计实践——最长公共子序列
文章链接：http://soscw.com/index.php/essay/50616.html

亲，登录后才可以留言！

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

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

1.问题

2.解析

3.设计

4.分析

5.源码

评论

热门文章

推荐文章

最新文章

置顶文章