动态规划:求字符串最长公共子串/最长公共子序列 | code_nie's blog

动态规划:求字符串最长公共子串/最长公共子序列

动态规划:求字符串最长公共子串/最长公共子序列

1. 两者的区别

  • 最长公共子串(Longest Common Substring)与最长公共子序列(Longest Common Subsequence)的区别: 子串要求在原字符串中是连续的,而子序列则只需保持相对顺序一致,并不要求连续。例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么,{a, 1, 1}是X和Y的最长公共子序列,但不是它们的最长公共字串。

2. 求字符串最长公共子序列

2.1 只需要得到最长公共子序列的长度

  • 这是典型的动态规划问题,两个字符串的长度分别是a & b, 得到长和宽分分别为a + 1和b + 1的二维数组,顺序遍历,表达式为:
  • 时间复杂度O(ab),空间复杂度为O(ab),比递归省事多了。
  • Example: 交大OJ-1065. 小M的生物实验1
    解题代码如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

string a, b;
vector<vector<int> > similarity;

int getSimilarity()
{
int lenA = a.size();
int lenB = b.size();
for (int i = 0; i < lenA; i++) {
for (int j = 0; j < lenB; j++) {
if (a[i] == b[j]) {
similarity[i + 1][j + 1] = similarity[i][j] + 1;
}
else {
similarity[i + 1][j + 1] = max(similarity[i][j + 1], similarity[i + 1][j]);
}
}
}
return similarity[lenA][lenB];
}

int main()
{
cin >> a >> b;
similarity = vector<vector<int> >(a.size() + 10, vector<int>(b.size() + 10, 0));
int result;
result = getSimilarity();
cout << result << endl;
return 0;
}

2.2 输出一个最长公共子序列的内容

2.3 输出所有的最长公共子序列的内容

3. 最长公共子串

参考博客:
动态规划:求最长公共子串/最长公共子序列