#include <bits/stdc++.h> using namespace std; int n, m, q, dp[3005][3005], l1, l2, r1, r2; string a, b; int lcs() { for(int i = l1; i <= r1; i++) { for(int j = l2; j <= r2; j++) { dp[i][j] = (a[i - 1] == b[j - 1]); if(i > l1 && j > l2) dp[i][j] += dp[i - 1][j - 1]; if(i > l1 && dp[i][j] < dp[i - 1][j]) dp[i][j] = dp[i - 1][j]; if(j > l2 && dp[i][j] < dp[i][j - 1]) dp[i][j] = dp[i][j - 1]; } } return dp[r1][r2]; } int main() { ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0); cin >> n >> m >> q >> a >> b; while(q--) { cin >> l1 >> r1 >> l2 >> r2; cout << lcs() << "\n"; } }
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 | #include <bits/stdc++.h> using namespace std; int n, m, q, dp[3005][3005], l1, l2, r1, r2; string a, b; int lcs() { for(int i = l1; i <= r1; i++) { for(int j = l2; j <= r2; j++) { dp[i][j] = (a[i - 1] == b[j - 1]); if(i > l1 && j > l2) dp[i][j] += dp[i - 1][j - 1]; if(i > l1 && dp[i][j] < dp[i - 1][j]) dp[i][j] = dp[i - 1][j]; if(j > l2 && dp[i][j] < dp[i][j - 1]) dp[i][j] = dp[i][j - 1]; } } return dp[r1][r2]; } int main() { ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0); cin >> n >> m >> q >> a >> b; while(q--) { cin >> l1 >> r1 >> l2 >> r2; cout << lcs() << "\n"; } } |