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

using namespace std;
using namespace __gnu_pbds;

constexpr int M=3e3+7;

int dp[M][M];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	string s1, s2;
	int n, m, q, a, b, c, d;
	
	cin >> n >> m >> q >> s1 >> s2;
	
	while(q--){
		cin >> a >> b >> c >> d;
		
		for(int i=a-1; i<=b+1; i++) for(int j=c-1; j<=d+1; j++) dp[i][j]=0;
		
		for(int i=a; i<=b; i++){
			for(int j=c; j<=d; j++){
				dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
				if(s1[i-1] == s2[j-1]) dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
			}
		}
		
		cout << dp[b][d] << '\n';
	}
	
	return 0;
}