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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define Max 3003
char t1[Max];
char t2[Max];

int Map[Max][Max];
int N, M, Q, q;

struct Skip {
    int right;
    int bottom;
    bool isSkip;
};

Skip Skips[Max][Max];

struct Mem {
    int q;
    int count;
};

Mem Memory[Max][Max];

int max(int x, int y) {
    return x > y ? x : y;
}

void countSubSequence(char t1[], char t2[]) {
    for (int m = 0; m < M; m++) {
        for (int n = 0; n < N; n++) {
            if (t1[n] == t2[m]) {
                Map[n + 1][m + 1] = Map[n][m] + 1;
                Skips[n + 1][m + 1].isSkip = true;
                //printf("^%d ", Map[n + 1][m + 1]);
            }
            else {
                Map[n + 1][m + 1] = max(Map[n + 1][m], Map[n][m + 1]);
                //printf(" %d ", Map[n + 1][m + 1]);
            }
        }
        //printf("\n");
    }
    //count skips horizontally
    for (int m = 0; m < M; m++) {
        int currentSkipTo = -1;
        for (int n = N - 1; n >= 0; n--) {
            if (Skips[n + 1][m + 1].isSkip)
                currentSkipTo = n + 1;
            else
                Skips[n + 1][m + 1].right = currentSkipTo;
        }
    }
    //count skips vertically
    for (int n = 0; n < N; n++) {
        int currentSkipTo = -1;
        for (int m = M - 1; m >= 0; m--) {
            if (Skips[n + 1][m + 1].isSkip)
                currentSkipTo = m + 1;
            else
                Skips[n + 1][m + 1].bottom = currentSkipTo;
        }
    }
}

int count(int f1, int t1, int f2, int t2) {
    if (f1 == -1 || f2 == -1)
        return 0;
    if (f1 > t1 || f2 > t2)
        return 0;
    if (Memory[f1][f2].q == q && Memory[f1][f2].count > 0)
        return Memory[f1][f2].count;
    if (Skips[f1][f2].isSkip) {
        int r = 1 + count(f1 + 1, t1, f2 + 1, t2);
        Memory[f1][f2].q = q;
        Memory[f1][f2].count = r;
        return r;
    }
    int r1 = count(Skips[f1][f2].right, t1, f2, t2);
    int r2 = count(f1, t1, Skips[f1][f2].bottom, t2);
    int r3 = count(f1 + 1, t1, f2 + 1, t2);
    int rMax = max(r1, max(r2, r3));
    Memory[f1][f2].q = q;
    Memory[f1][f2].count = rMax;
    return rMax;
}

int main()
{
    scanf("%d %d %d", &N, &M, &Q);
    for (int i = 0; i < N; i++)
        scanf(" %c", &t1[i]);
    t1[N] = 0;
    for (int i = 0; i < M; i++)
        scanf(" %c", &t2[i]);
    t2[M] = 0;
    countSubSequence(t1, t2);
    for (q = 0; q < Q; q++) {
        int f1, t1, f2, t2;
        scanf(" %d %d %d %d", &f1, &t1, &f2, &t2);
        printf("%d\n", count(f1, t1, f2, t2));
    }
    return 0;
}