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
#include <bits/stdc++.h>
using namespace std;
const int SIZE=601;
int n,m,k;
string s1,s2;
int a1,b1,a2,b2;
int arr[SIZE][SIZE];
int lcs(int a,int b,int c,int d){
	int best=0;
	for(int i=a;i<=b;++i){
		for(int j=c;j<=d;++j){
			if(s1[i]==s2[j]) arr[i][j]=arr[i-1][j-1]+1;
			else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
			best=max(best,arr[i][j]);
		}
	}
	return best;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k;
	cin>>s1>>s2;
	s1="$"+s1;
	s2="$"+s2;
	for(int i=0;i<k;++i){
		cin>>a1>>b1>>a2>>b2;
		cout<<lcs(a1,b1,a2,b2)<<"\n";
		memset(arr,0,sizeof(arr));
	}
}