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
#include <iostream>
#include <string>

using namespace std;

string s1, s2, sLCS; // zmienne globalne

// Funkcja oblicza dlugosc LCS dla temp1 i temp2
// i - indeks startu w temp1
// j - indeks startu w temp2
//----------------------------------------
int LCS ( int i, int j )
{
  if( !s1 [ i ] || !s2 [ j ] ) {
        return 0;
  }
  else if( s1 [ i ] == s2 [ j ] ){
     return LCS ( i + 1, j + 1 );
  }
  else {
        return max ( LCS ( i+1, j ), LCS ( i, j+1 ) );
  }
}

int main( )
{
  int i, j;
  int n,m,q;
  cin >> n >> m >> q;
  cin >> s1 >> s2;
  for(int k=0; k<q; ++k){
    int x1,x2,y1,y2;
    cin >> x1 >> x2 >> y1 >> y2;
    string temp1 = "", temp2="";
    for(int z=x1-1; z<=x2-1; ++z){
        temp1+=s1[z];
    }
    for(int z=y1-1; z<=y2-1; ++z){
        temp2+=s2[z];
    }
    ////
    sLCS = ""; i = j = 0;
    while( temp1 [ i ] && temp2 [ j ] )
        if( temp1 [ i ] == temp2 [ j ] )
        {
          sLCS += temp1 [ i ]; i++; j++;
        }
        else if( LCS ( i+1, j ) <= LCS ( i, j+1 ) ) j++; else i++;
    cout << sLCS.length( ) << endl;
    ////
  }

  return 0;
}