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
81
82
83
84
85
86
87
88
89
#include <iostream>

using namespace std;

#define MAX_TEKST  3002
#define MAX_Q 100005

int n, m;
long q;
char s[ MAX_TEKST ];
char t[ MAX_TEKST ];

int i[ MAX_Q ];
int j[ MAX_Q ];
int k[ MAX_Q ];
int l[ MAX_Q ];

int **tab;

void wczytaj()
{
    cin >> n >> m >> q;
    cin >> s;

    cin >> t;

    for( long a = 0; a < q; a ++ )
    {
        cin >> i[ a ];
        cin >> j[ a ];
        cin >> k[ a ];
        cin >> l[ a ];
    }
}

int policz( int ii, int jj, int kk, int ll )
{
    int a, b;

   for( int a = ii - 1; a <= jj; a ++ )
        tab[ a ][ kk - 1 ] = 0;
   for( int b = kk - 1 ; b <= ll; b ++ )
        tab[ ii - 1 ][ b ] = 0;


    for( a = ii; a <= jj; a ++ )
        for( b = kk; b <= ll; b ++)
        {
            if( s[ a - 1 ] == t[ b - 1] )
                tab[ a ][ b ] = tab[ a - 1][ b - 1] + 1;
            else
                tab[ a ][ b ] = max( tab[a - 1][ b ], tab[ a ][ b - 1] );
        }
    return tab[ jj ][ ll ];
}


void init_tab()
{
    tab = (int**) malloc( sizeof( int*) * MAX_TEKST );
    for( int a = 0; a < MAX_TEKST;  a ++ )
    {
        tab[ a ] = (int*) malloc( sizeof( int*) * MAX_TEKST );
    }

   for( int a = 0; a <= n; a ++ )
        tab[ a ][ 0 ] = 0;
   for( int b = 0; b <= m; b ++ )
        tab[ 0 ][ b ] = 0;

}

int main()
{
    std::ios_base::sync_with_stdio( false);
    std::cin.tie(NULL);
    wczytaj();


    init_tab();
    int a, b;

     for( long a = 0; a < q; a ++ )
     {
        cout << policz( i[ a ], j[ a ], k[ a ], l[ a ] ) << '\n';
     }

    return 0;
}