1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
const int mx=3005;
int dp[mx][mx];
int n,m,q,poc1,poc2,kon1,kon2;
string s1,s2;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>q;
    cin>>s1>>s2;
    for(int i=0;i<q;++i){
        cin>>poc1>>kon1>>poc2>>kon2;
        for(int j=poc2-1;j<=kon2;++j)dp[poc1-1][j]=0;
        for(int j=poc1-1;j<=kon1;++j)dp[j][poc2-1]=0;
        for(int j=poc1;j<=kon1;++j){
            for(int k=poc2;k<=kon2;++k){
                if(s1[j-1]==s2[k-1])dp[j][k]=1+dp[j-1][k-1];
                else dp[j][k]=max(dp[j-1][k],dp[j][k-1]);
            }
        }
        cout<<dp[kon1][kon2]<<"\n";
    }
}