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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

void get_LCS_tab(const char* a, const char* b, int alen, int blen, vector<vector<int>>& dp){
    for(int i=0;i<=alen;i++)
        dp[i][0]=0;
    for(int j=0;j<=blen;j++)
        dp[0][j]=0;

    for(int i=1;i<=alen;i++)
        for(int j=1;j<=blen;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]);
}

struct Query{
    int i,j,k,l,id,result;
};

char s[3005], t[3005];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n,m,q;
    cin >> n >> m >> q;
    cin >> s >> t;

    vector<Query>Q(q);
    for(int ii=0;ii<q;ii++){
        cin >> Q[ii].i >> Q[ii].j >> Q[ii].k >> Q[ii].l;
        Q[ii].i--;
        Q[ii].j--;
        Q[ii].k--;
        Q[ii].l--;
        Q[ii].id=ii;
    }
    sort(Q.begin(), Q.end(), [](const Query& q1, const Query& q2){
        if(q1.i!=q2.i)
            return q1.i < q2.i;
        return q1.k < q2.k;
    });

    vector<vector<int>>dp(3005, vector<int>(3005));
    for(int it=0;it<q;){
        int i=Q[it].i;
        int k=Q[it].k;
        int maxJ=Q[it].j, maxL=Q[it].l;

        for(int it2=it+1;it2<q && Q[it2].i==i && Q[it2].k==k;it2++){
            maxJ = max(maxJ, Q[it2].j);
            maxL = max(maxL, Q[it2].l);
        }
        get_LCS_tab(s+i, t+k, maxJ-i+1, maxL-k+1, dp);

        for(;it<q && Q[it].i==i && Q[it].k==k;it++)
            Q[it].result = dp[Q[it].j-i+1][Q[it].l-k+1];
    }


    sort(Q.begin(), Q.end(), [](const Query& q1, const Query& q2){
        return q1.id < q2.id;
    });
    for(int i=0;i<q;i++)
        cout << Q[i].result << "\n";
    
    return 0;
}