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
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
// Artur Kraska, II UWr

#include <bits/stdc++.h>

#define forr(i, n)                  for(int i=0; i<n; i++)
#define FOREACH(iter, coll)         for(auto iter = coll.begin(); iter != coll.end(); ++iter)
#define FOREACHR(iter, coll)        for(auto iter = coll.rbegin(); iter != coll.rend(); ++iter)
#define lbound(P,R,PRED)            ({typeof(P) X=P,RRR=(R), PPP = P; while(PPP<RRR) {X = (PPP+(RRR-PPP)/2); if(PRED) RRR = X; else PPP = X+1;} PPP;})
#define testy()                     int _tests; scanf("%d", &_tests); FOR(_test, 1, _tests)
#define CLEAR(tab)                  memset(tab, 0, sizeof(tab))
#define CONTAIN(el, coll)           (coll.find(el) != coll.end())
#define FOR(i, a, b)                for(int i=a; i<=b; i++)
#define FORD(i, a, b)               for(int i=a; i>=b; i--)
#define MP                          make_pair
#define PB                          push_back
#define ff                          first
#define ss                          second
#define deb(X)                      X;

#define M 1000000007
#define INF 1000000007LL

using namespace std;

int n, m, k, numer = 1;
int tab[3005][3005], tab2[3005][3005], byl[3005][3005];
char sl1[3005], sl2[3005], res[1000007];
int dokad[3005];

struct zapytanie
{
    int p1, k1, p2, k2, id;
};
zapytanie z;
vector <zapytanie> v;

bool comp(zapytanie &a, zapytanie &b)
{
    if(a.p1 != b.p1)
        return a.p1 > b.p1;
    return a.p2 > b.p2;
}

int main()
{
    scanf("%d %d %d", &n, &m, &k);
    scanf("%s %s", (char*)sl1+1, (char*)sl2+1);
    FOR(i, 1, n)
        FOR(j, 1, m)
            tab[i][j] = max(max(tab[i-1][j], tab[i][j-1]), sl1[i] == sl2[j] ? tab[i-1][j-1]+1 : 0);
    FOR(id, 1, k)
    {
        scanf("%d %d %d %d", &z.p1, &z.k1, &z.p2, &z.k2);
        z.id = id;
        v.PB(z);
    }
    sort(v.begin(), v.end(), comp);

    while(!v.empty())
    {
        z = v.back();
        v.pop_back();
//        cout << "obrabia punkt " << z.p1 << " " << z.p2 << endl;

        vector <zapytanie> todo;
        todo.PB(z);
        while(!v.empty() && v.back().p1 == z.p1 && v.back().p2 == z.p2)
        {
            todo.PB(v.back());
            v.pop_back();
        }

        FOR(i, z.p1-1, n)
            tab2[i][z.p2-1] = tab[z.p1-1][z.p2-1];
        FOR(i, z.p2-1, m)
            tab2[z.p1-1][i] = tab[z.p1-1][z.p2-1];
        FOR(i, z.p1, n)
            dokad[i] = 0;

        for(auto zap : todo)
            dokad[zap.k1] = max(dokad[zap.k1], zap.k2);

        FORD(i, n, z.p1)
        {
            dokad[i] = max(dokad[i], dokad[i+1]);
//            cout << "dokad[" << i << "] = " << dokad[i] << endl;
        }

        FOR(i, z.p1, n)
            FOR(j, z.p2, dokad[i])
            {
//                cout << "update " << i << " " << j << endl;
                tab2[i][j] = max(max(tab2[i-1][j], tab2[i][j-1]), sl1[i] == sl2[j] ? tab2[i-1][j-1]+1 : 0);
            }

        for(auto zap : todo)
        {
            res[zap.id] = tab2[zap.k1][zap.k2] - tab2[zap.p1-1][zap.p2-1];
        }
    }

    FOR(i, 1, k)
        printf("%d\n", res[i]);

    return 0;
}