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
#include <cstdio>
#include <vector>

using namespace std;

int main() {
  int n, m, q; scanf("%d %d %d", &n, &m, &q);
  char* a = new char[n+1];
  char* b = new char[m+1];
  scanf("%s ", a);
  scanf("%s ", b);

  for (int qq=0; qq<q; ++qq) {
    int x, y, z, t; scanf("%d %d %d %d", &x, &y, &z, &t);
    --x; --z;
    y = y - x;
    t = t - z;
    vector<int> curr(y+1, 0), next(y+1);
/* 
    for (int i=0; i<=y; ++i) printf("      %d  ", curr[i]);
    printf("\n");
*/
    for (int j=1; j<=t; ++j) {
      next[0] = 0;
//      printf("      %d  ", 0);
      for (int i=1; i<=y; ++i) {
        next[i] = max(next[i-1], curr[i]);
        if (a[x+i-1] == b[z+j-1]) {
          next[i] = max(next[i], curr[i-1] + 1);
        }
//        printf("(%c=%c) %d  ", a[x+i-1], b[z+j-1], next[i]);
      }
//      printf("\n");
      swap(curr, next);
    }
      
    printf("%d\n", curr[y]);
  }
  return 0;
}