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
// w zadaniu użyłem kodu z https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/

#include <bits/stdc++.h>

using namespace std;

int n, m, q;

char s[3000];
char t[3000];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> q;

	cin >> s >> t;

	//cout << s << " " << t << endl;

	while(q--){
		int i, j, k, l;
		cin >> i >> j >> k >> l;
		vector < int > a, b;
		for (int x = i - 1; x < j; ++x)
		{
			a.push_back(s[x]);
			//cout << s[x];
		}
		//cout << endl;
		for (int x = k - 1; x < l; ++x)
		{
			b.push_back(t[x]);
		//	cout << t[x];
		}
		//cout << endl;

		// muszą znaleźć najdłuższy wspólny podciąg słów s i t

		int m1, n1;
		m1 = j - i + 1;
		n1 = l - k + 1;

		int T[m1 + 1][n1 + 1];
	    for (int i1 = 0; i1 < m1 + 1; i1++)  
	    {  
	    	//cout << "A" << endl;
	        for (int j1 = 0; j1 < n1 + 1; j1++)  
	        {  
		        if(i1 == 0 or j1 == 0){
					T[i1][j1] = 0;  
				}
				else if (a[i1 - 1] == b[j1 - 1]) {
				    T[i1][j1] = T[i1 - 1][j1 - 1] + 1;  
				}

				else{      	
						T[i1][j1] = max(T[i1 - 1][j1], T[i1][j1 - 1]);  
					}
			}  
		}  

	    cout << T[m1][n1] << endl;
	}
}