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
#include <bits/stdc++.h>

int n, m, q;
int a, b, c, d;
char s[3003];
char t[3003];

int dp[603][603];

int main()
{
    scanf("%d%d%d", &n, &m, &q);
    scanf("%s", s);
    scanf("%s", t);
    while(q--)
    {
        scanf("%d%d%d%d", &a, &b, &c, &d);
        for(int i=a; i<=b; i++)
            for(int j=c; j<=d; j++)
                if(s[i-1]==t[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                    dp[i][j]=std::max(dp[i-1][j], dp[i][j-1]);
        printf("%d\n", dp[b][d]);
        for(int i=a; i<=b; i++)
            for(int j=c; j<=d; j++)
                dp[i][j]=0;
    }
}