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
#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef vector<int> vint;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back

constexpr int M=4096;
int dp[M][M];
//bitset <4> p[4096][4096]; // 0-> (i-1),   1-> (j-1),   2->(i-1,j-1)+1
bitset<M> o[M];
int n, m, T, wyn;
int p1, p2, q1, q2;
char a[M], b[M];
queue <pii> q;
pii x;

void cleer(){
	while(!q.empty()) q.pop();
}

void add(int x, int y){
	if(x<p1 or y<p2) return;
	if(!o[x][y]){
		o[x][y]=1;
		q.push(mp(x,y));
	}
}

int main(){
	scanf("%d%d%d",&n,&m,&T);
	scanf(" %s",a+1);
	scanf(" %s",b+1);
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
			if(a[i]==b[j]) dp[i][j]=dp[i-1][j-1]+1;
		}
	}
	while(T--){
		scanf("%d%d%d%d",&p1,&q1,&p2,&q2);
		--p1; --p2;
		add(q1,q2);
		wyn=dp[q1][q2];
		while(!q.empty()){
			x=q.front();
			q.pop();
			if(x.ff==p1 or x.ss==p2){
				wyn=min(wyn,dp[x.ff][x.ss]);
				//printf("biorę wynik z %d %d\n",x.ff,x.ss);
			}else{
				if(dp[x.ff][x.ss]==dp[x.ff-1][x.ss]) add(x.ff-1,x.ss);
				if(dp[x.ff][x.ss]==dp[x.ff][x.ss-1]) add(x.ff,x.ss-1);
				if(a[x.ff]==b[x.ss]) add(x.ff-1,x.ss-1);
			}
		}
		printf("%d\n",dp[q1][q2]-wyn);
		for(int i=p1;i<=q1;++i) o[i].reset();
	}
	
	
	
	return 0;
}
/*
5 6 7
abaab
babbaa
1 5 1 6
1 3 2 4
2 5 2 5
1 4 2 5
2 5 3 6
2 2 5 6
3 4 2 2
*/