LCS与编辑距离以及MCSS

jobs

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
69
// 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
60
#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