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<iostream>

using namespace std;

int main()
{
	int n, m, q; cin >> n >> m >> q;
	int t[n+1][m+1];
	for(int i = 0; i <= n; i++)	t[i][0] = 0;
	for(int i = 0; i <= m; i++)	t[0][i] = 0;
	
	string s, k;

	cin >> s;
	cin >> k;
	
	
	for(int i = 1; i <= n; i++)	for(int j = 1; j <= m; j++)	
	if(s[i-1]==k[j-1])	t[i][j] = t[i-1][j-1]+1;
	else t[i][j] = max(t[i-1][j],t[i][j-1]);
	
		
	for(int i=0; i<q; i++)
	{
		int a,b,c,d; cin >> a >> b >> c >> d;
		int ans = t[b][d]-t[a][c];
		if (t[a-1][c]<t[a][c] && t[a][c-1]<t[a][c]) ans++;
		cout << ans <<endl;
	}
	
	return 0;
}