aoj

ALDS1_10_C Longest Common Subsequence

ALDS1_10_C Longest Common Subsequence
Feb. 2, 2020, 1:52 p.m.

目次

解答

タイムアウトになる解答.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
int lcs(string &s1, string &s2, int i1, int i2) {
    if (i1 >= s1.length() || i2 >= s2.length()) return 0;
    if (s1[i1] == s2[i2]) return 1 + lcs(s1, s2, i1+1, i2+1);
    return max(
        lcs(s1, s2, i1 + 1, i2),
        lcs(s1, s2, i1, i2 + 1)
    );
}

int main(void) {
    int n;
    string s1, s2;

    cin >> n;
    loop(i, 0, n) {
        cin >> s1 >> s2;
        cout << lcs(s1, s2, 0, 0) << endl;
    }
}

解答

動的計画法を使ってO(MN)まで高速化した解法.

 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
#define MAX 1000



int lcs(string &s1, string &s2) {
    int dp[MAX+1][MAX+1];
    int l1 = s1.length();
    int l2 = s2.length();
    int maxl = 0;

    s1 = ' ' + s1;
    s2 = ' ' + s2;

    loop(i, 0, l1+1) {
        dp[i][0] = 0;
    }
    loop(j, 0, l2+1) {
        dp[0][j] = 0;
    }

    loop (i, 1, l1+1) {
        loop (j, 1, l2+1) {
            if (s1[i] == s2[j]) dp[i][j] = 1 + dp[i-1][j-1];
            else dp[i][j] = max(
                dp[i-1][j],
                dp[i][j-1]
            );

            maxl = max(maxl, dp[i][j]);
        }

    }

    return maxl;
}

int main(void) {
    int n;
    string s1, s2;

    cin >> n;
    loop(i, 0, n) {
        cin >> s1 >> s2;
        cout << lcs(s1, s2) << endl;
    }
}