跳转至

最长公共子序列

 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
//动态规划求解并输出其中一个LCS 
#include <iostream>
#include <string>

using namespace std;

int max(int a, int b) {  //返回a，b中值较大的元素 
    return (a > b) ? a : b;
}

int lcs_length(string sx, string sy, int **c) { //动态规划计算LCS的长度
    int xlen = sx.length();
    int ylen = sy.length();
    //c[i][j]记录sx[i]与sy[j]的LCS的长度  
    for (int i = 0; i < xlen + 1; i++) {
        for (int j = 0; j < ylen + 1; j++) {
            if (i == 0 || j == 0) {             //情形1：i = 0或j = 0; 
                c[i][j] = 0;
            }
            else if (sx[i - 1] == sy[j - 1]) { //情形2：i, j > 0且sx[i-1] = sy[j-1] 
                c[i][j] = c[i - 1][j - 1] + 1;  
            }
            else {                             //情形3：i, j > 0且sx[i-1] != sy[j-1] 
                c[i][j] = max(c[i][j - 1], c[i - 1][j]);
            }
        }
    }
    return c[xlen][ylen];
}

void print_lcs(int **c, string sx, int i, int j, string &s) { //递归将sx与sy的一个LCS赋值给字符串s 
    if (i == 0 || j == 0) {             //对应lcs_length()中的情形1 
        return;
    }   
    if (c[i][j] == c[i - 1][j]) {       //对应lcs_length()中的情形3 
        print_lcs(c, sx, i - 1, j, s);
    }
    else if (c[i][j] == c[i][j - 1]) {  //对应lcs_length()中的情形3  
        print_lcs(c, sx, i, j - 1, s);
    }
    else {                              //对应lcs_length()中的情形2 
        print_lcs(c, sx, i - 1, j - 1, s);
        s += sx[i - 1];
    }
}

int main() {
    string sx, sy;
    cout << "Please enter the string x and the string y:" << endl;
    cout << "sx: ";
    cin >> sx;
    cout << "sy: ";
    cin >> sy;
    int xlen = sx.length();
    int ylen = sy.length();
    int **c = new int *[xlen + 1];     //为动态规划表开空间 
    for (int i = 0; i < xlen + 1; i++) {
        c[i] = new int [ylen + 1];
    }
    int maxlen = lcs_length(sx, sy, c);
    cout << "The length of LCS is " << maxlen << endl;
    string s;
    print_lcs(c, sx, xlen, ylen, s);
    cout << "The LCS of sx and sy is: " << s << endl;
    for (int i = 0; i < xlen + 1; i++) { //释放占用的空间 
        delete[]c[i];
    }
    delete[]c;
    return 0;
}