[C++]学习字符串最长公共子序列（非连续）算法_c++ 最大非连续子序列

测试代码

#include "stdafx.h"
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <algorithm>
using std::cin;
using std::cout;
using std::reverse;
using std::endl;
using std::max;
using std::string;
using std::vector;

//计算字符串str1和str2的最长公共子序列
void LRC(string str1, string str2, string &resultStr) {
    int len1 = str1.length();
    int len2 = str2.length();
    vector<vector<int>> resultVector(len1+1,vector<int>(len2+1));
    //初始化第0行
    for (int i = 0; i < len2; i++) {
        resultVector[0][i] = 0;
    }
    //初始化第0列
    for (int i = 0; i < len1; i++) {
        resultVector[i][0] = 0;
    }
    /*
        计算表达式
                            |--  result[i-1,j-1] + 1              x[i] == y[j]
        resultVector[i][j] =| 
                            |--  max(result[i-1,j],result[i,j-1]  x[i] != y[j]
    */
    //str1
    for (int i = 1; i < len1 + 1; i++) {
        //str2
        for (int j = 1; j < len2; j++) {
            //x[i] == y[j]
            if (str1.at(i - 1) == str2.at(j - 1)) {
                resultVector[i][j] = resultVector[i - 1][j - 1] + 1;
            }
            //x[i] != y[j]
            else {
                resultVector[i][j] = max(resultVector[i - 1][j], resultVector[i][j - 1]);
            }
        }
    }
    //输出结果矩阵
    cout << "计算中间结果矩阵: " << endl;
    cout << "\t\t";
    for (int i = 0; i < len2; i++)
        cout << str2.at(i) << "\t";
    cout << endl;
    for (int i = 0; i < len1+1; i++) {
        if (i == 0)
            cout << "\t";
        else
            cout << str1.at(i - 1)<<"\t";
        for (int j = 0; j < len2+1; j++) {
            cout << resultVector[i][j] << "\t";
        }
        cout << endl;
    }
    //计算公共子序列
    while (len1 != 0 && len2 != 0) {
        if (str1.at(len1 - 1) == str2.at(len2 - 1)) {
            resultStr.push_back(str1.at(len1 - 1));
            len1--;
            len2--;
        }
        else if (resultVector[len1][len2 - 1] > resultVector[len1 - 1][len2]) {
            len2--;
        }
        else {
            len1--;
        }
    }
    //字符串翻转
    reverse(resultStr.begin(),resultStr.end());
}


int main()
{
    string str1 = "abcdef";
    string str2 = "fcddsefe";
    string resultStr;
    LRC(str1, str2, resultStr);
    cout << "str1:\t" << str1 << endl;
    cout << "str2:\t" << str2 << endl;
    cout << "lrc:\t" << resultStr << endl;
    system("pause");
    return 0;
}
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

测试结果