LCS与编辑距离以及MCSS

LCS(Longest Common Subsequence) 问题即最长公共子序列问题,就是两个字符串的 子序列 而不是 子串 的最大的长度。

之前的 LIS 问题也可以通过构造两个字符串来解决,一个是原串,一个是排序后的递增串,然后通过两个字符串求 LCS 的问题。

算法流程

  • 设定 dp[i][j] 为str(0…i) 与 patten(0…j) 的最长子公共子序列的长度
  1. 初始化 数组的 0 下标为零,然后更新 dp[i][j];
  2. str[i] == patten[j]dp[i][j] = dp[i-1][j-1],若 str[i] != patten[j]dp[i][j] = max(dp[i][j-1],dp[i-1][j])
  3. 迭代更新 dp[i][j]

最长子序列输出

  1. str[i] == patten[j],则输出 str[i] (导致反向输出)
  2. str[i] != patten[j],则判断 dp[i][j] 是等于上方的(i–)还是下方的(j–),然后移到该方向。

参考代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// LCS 问题

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

void lcs(const string &str, const string &patten)
{
const int strSize = str.length();
const int pattenSize = patten.length();

int dp[strSize+1][pattenSize+1] = {0};

for(int i = 1; i <= strSize; ++i)
{
for(int j = 1; j <= pattenSize; ++j)
{
if(str[i-1] == patten[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
}
else
{
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
}
int i = strSize;
int j = pattenSize;
vector<char> re;
while(i > 0 && j > 0)
{
if(str[i-1] == patten[j-1])
{
re.push_back(str[i-1]);
--i;
--j;
}
else if(dp[i][j] == dp[i-1][j])
{
--i;
}
else if(dp[i][j] == dp[i][j-1])
{
--j;
}
}

reverse(re.begin(),re.end());
for(auto c:re)
{
cout<<c;
}
cout<<endl;

}

int main(int argc, char *argv[])
{
string str = "kangqingfei";
string patten = "ng";

lcs(str,patten);

return 0;
}

编辑距离问题(Edit Distance)

编辑距离和LCS很像,只是更新 dp[i][j] 的时候略有不同而已

算法流程

  • 设定 dp[i][j] 为 str1(0…i) 与 str2(0…j) 的编辑距离
  1. 初始化 dp[0][j] 和 dp[i][0] 为 j 和 i 其含义为,一个字符串与一个空串的编辑距离为字符串本身的长度
  2. 更新dp[i][j],更新规则为,若 str1[i] == str2[j] 则dp[i][j] = dp[i-1][j-1] 若 str1[i] != str2[j] 则考虑 str1 不变,str2 可以通过 增加(dp[i-1][j] + 1) 删除(dp[i][j-1] + 1) 替换(dp[i-1][j-1] + 1) 变到str1
  3. 迭代更新 dp[i][j], 输出dp[iMax][jMax] 即为编辑距离

参考代码

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
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

editDistance(string str1, string str2)
{
const int length1 = str1.length();
const int length2 = str2.length();

int dp[length1+1][length2+1] = {0};

for(int i = 0; i <= length1; ++i)
{
dp[i][0] = i;
}
for(int i = 0; i <= length2; ++i)
{
dp[0][i] = i;
}
for(int i = 0; i <= length1; ++i)
{
for(int j = 0; j <= length2; ++j)
{
if(str1[i] == str2[j])
{
dp[i][j] = dp[i-1][j-1];
}
else
{// 增加 删除 替换
dp[i][j] = min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1]) + 1;
}
}
}
cout<<dp[length1][length2]<<endl;

}

int main(int argc, char *argv[])
{
string str1 = "kangqingfei";
string str2 = "kangqingfeng";

editDistance(str1,str2);

return 0;
}

最长公共子串问题

该问题与 LCS 问题的区别就在于 是否连续
若可以连续就是子串 否则就是子序列
对于子串的解法与子序列的解法基本一致 区别就在于

1
2
3
4
if(str1[i] != str2[j])
dp[i][j] = 0
else if(str1[i] == str2[j])
dp[i][j] = dp[i-1][j-1]+1

最后通过 遍历 dp[i][j] 来获得最大的子串长度,然后得到子串
在空间优化上面可以通过滚动数组来节省空间

最大连续序列求和(Maximum Contiguous Subsequence Sum)MCSS 问题

该问题为求一个序列的所有子序列中 和最大 的那个子序列。
该问题为简单的动态规划问题

参考代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <vector>

using namespace std;


int mcss(vector<int> &arr)
{
const int len = arr.size()+1;
int dp[len];
int maxSum = 0;
dp[0] = 0;
for(int i = 1; i < len; ++i)
{
dp[i] = dp[i-1] > 0 ? arr[i-1]+dp[i-1]:arr[i-1];
if(dp[i] > maxSum)
maxSum = dp[i];
}
return maxSum;

}

int mcssPlus(vector<int> &arr)//空间优化版本
{
int maxSum = 0;
int tmpDp = 0;
for(int i = 0; i < arr.size(); ++i)
{
if(tmpDp > 0)
{
tmpDp += arr[i];
}
else
{
tmpDp = arr[i];
}
if(tmpDp > maxSum)
maxSum = tmpDp;
}

return maxSum;
}

// 6 -2 11 -4 13 -5 -2 -> 20
int main(int argc, char *argv[])
{
int count,tmp;
vector<int> arr;
cin>>count;
while(count--)
{
cin>>tmp;
arr.push_back(tmp);
}

cout<<mcssPlus(arr);

return 0;
}
T B
站点访问量: / , 本页阅读量:
T B