codeRoad/AlgorithmCourse/1022.cpp at main · madderscientist/codeRoad · GitHub

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
#include <bits/stdc++.h>
using namespace std;

unsigned short shareLen(string& a, string& b) {
    unsigned short la = a.length();
    unsigned short lb = b.length();
    // unsigned short** dp = new unsigned short*[la + 1];
    // for (int i = 0; i <= la; i++) {
    //     dp[i] = new unsigned short[lb + 1]{0};
    // }

    // for (int i = 1; i <= la; i++) {
    //     for (int j = 1; j <= lb; j++) {
    //         if (a[i-1] == b[j-1]) {
    //             dp[i][j] = dp[i-1][j-1] + 1;
    //         } else {
    //             dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    //         }
    //     }
    // }

    // unsigned short result = dp[la][lb];
    // for (int i = 0; i <= la; i++) delete[] dp[i];
    // delete[] dp;
    // return result;

    // unsigned short* dp = new unsigned short[lb + 1]{0};
    // unsigned short* dp2 = new unsigned short[lb + 1]{0};
    // for (int i = 1; i <= la; i ++) {
    //     for (int j = 1; j <= lb; j++) {
    //         if (a[i-1] == b[j-1]) {
    //             dp[j] = dp2[j-1] + 1;
    //         } else {
    //             dp[j] = max(dp2[j], dp[j-1]);
    //         }
    //     }
    //     unsigned short* temp = dp2;
    //     dp2 = dp;
    //     dp = temp;
    // }
    // auto result = dp2[lb];
    // delete[] dp;
    // delete[] dp2;
    // return result;

    unsigned short* dp = new unsigned short[lb + 1]{0};
    for (int i = 1; i <= la; i++) {
        unsigned short prev = 0;  // 代表 dp2[j-1]
        for (int j = 1; j <= lb; j++) {
            unsigned short tmp = dp[j];  // 记录当前 dp[j]，即 dp2[j]
            if (a[i - 1] == b[j - 1]) {
                dp[j] = prev + 1;
            } else {
                dp[j] = max(dp[j], dp[j - 1]);
            }
            prev = tmp;
        }
    }
    auto result = dp[lb];
    delete[] dp;
    return result;
}

int main() {
    int m;
    cin >> m;
    while (m--) {
        string a, b;
        cin >> a >> b;
        if (a.length() > b.length()) {
            cout << shareLen(a, b) << '\n';
        } else {
            cout << shareLen(b, a) << '\n';
        }
    }
    return 0;
}