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; } } 

## 解答

  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; } }