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
#include <algorithm>
#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define INT(x) int x; scanf("%d", &x)
#define STR(n,x) char x[n]; scanf("%s", x)

int res[3001][3001];

int go(char* a, int n, char* b, int m) {
	REP(i,n) REP(j,m) {
		res[i + 1][j + 1] = max(res[i][j + 1], res[i + 1][j]);
		if (a[i] == b[j]) res[i + 1][j + 1] = max(res[i + 1][j + 1], res[i][j] + 1);
	}
	return res[n][m];
}

int main() {
	INT(n);
	INT(m);
	INT(q);
	STR(3001, s);
	STR(3001, t);
	REP(qq,q) {
		INT(i);
		INT(j);
		INT(k);
		INT(l);
		--i;
		--k;
		printf("%d\n", go(s + i, j - i, t + k, l - k));
	}
}