#define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) constexpr int MAX_N = 3005; string s, t; int ih[MAX_N][MAX_N]; int iv[MAX_N][MAX_N]; struct Query { int e1, b2, e2, i; }; void alcs(int firstRow) { rep(j, 0, sz(t)+1) { ih[firstRow][j] = j; } rep(l, firstRow, sz(s)+1) { iv[l][0] = 0; } rep(l, firstRow+1, sz(s)+1) { rep(j, 1, sz(t)+1) { if (s[l-1] != t[j-1]) { ih[l][j] = max(iv[l][j-1], ih[l-1][j]); iv[l][j] = min(iv[l][j-1], ih[l-1][j]); } else { ih[l][j] = iv[l][j-1]; iv[l][j] = ih[l-1][j]; } } } } int query(int b1, int e1, int b2, int e2) { int ret = 0; while (b1 < e1 && b2 < e2) { if (s[e1-1] == t[e2-1]) { e1--; e2--; ret++; } else if (b2 < ih[e1][e2]) { e2--; } else { e1--; } } return ret; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int n, m, q; cin >> n >> m >> q >> s >> t; vector<vector<Query>> queries(n); Vi ans(q); rep(i, 0, q) { int b1, e1, b2, e2; cin >> b1 >> e1 >> b2 >> e2; b1--; b2--; queries[b1].pb({ e1, b2, e2, i }); } rep(firstRow, 0, n) { if (!queries[firstRow].empty()) { alcs(firstRow); each(e, queries[firstRow]) { ans[e.i] = query(firstRow, e.e1, e.b2, e.e2); } } } each(a, ans) { cout << a << '\n'; } return 0; }
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 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | #define _USE_MATH_DEFINES #include <bits/stdc++.h> #ifdef LOC #include "debuglib.h" #else #define deb(...) #define DBP(...) #endif using namespace std; using ll = long long; using Vi = vector<int>; using Pii = pair<int, int>; #define pb push_back #define mp make_pair #define x first #define y second #define rep(i, b, e) for (int i = (b); i < (e); i++) #define each(a, x) for (auto& a : (x)) #define all(x) (x).begin(), (x).end() #define sz(x) int((x).size()) constexpr int MAX_N = 3005; string s, t; int ih[MAX_N][MAX_N]; int iv[MAX_N][MAX_N]; struct Query { int e1, b2, e2, i; }; void alcs(int firstRow) { rep(j, 0, sz(t)+1) { ih[firstRow][j] = j; } rep(l, firstRow, sz(s)+1) { iv[l][0] = 0; } rep(l, firstRow+1, sz(s)+1) { rep(j, 1, sz(t)+1) { if (s[l-1] != t[j-1]) { ih[l][j] = max(iv[l][j-1], ih[l-1][j]); iv[l][j] = min(iv[l][j-1], ih[l-1][j]); } else { ih[l][j] = iv[l][j-1]; iv[l][j] = ih[l-1][j]; } } } } int query(int b1, int e1, int b2, int e2) { int ret = 0; while (b1 < e1 && b2 < e2) { if (s[e1-1] == t[e2-1]) { e1--; e2--; ret++; } else if (b2 < ih[e1][e2]) { e2--; } else { e1--; } } return ret; } int main() { cin.sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(10); int n, m, q; cin >> n >> m >> q >> s >> t; vector<vector<Query>> queries(n); Vi ans(q); rep(i, 0, q) { int b1, e1, b2, e2; cin >> b1 >> e1 >> b2 >> e2; b1--; b2--; queries[b1].pb({ e1, b2, e2, i }); } rep(firstRow, 0, n) { if (!queries[firstRow].empty()) { alcs(firstRow); each(e, queries[firstRow]) { ans[e.i] = query(firstRow, e.e1, e.b2, e.e2); } } } each(a, ans) { cout << a << '\n'; } return 0; } |