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
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
string s1,s2;
int main()
{
	ios_base::sync_with_stdio(false);
	cin>>n>>m>>q;
	cin>>s1;
	cin>>s2;
	for(int qq=0;qq<q;++qq)
	{
		int b,e,x,y;
		cin>>b>>e>>x>>y;
		--b;
		--e;
		--x;
		--y;
		string t1="#",t2="#";
		for(int i=b;i<=e;++i)	t1+=s1[i];
		for(int i=x;i<=y;++i)	t2+=s2[i];
		vector<vector<int>> dp(e-b+2,vector<int>(y-x+2,0));
		for(int i=1;i<=e-b+1;++i)
		{
			for(int j=1;j<=y-x+1;++j)
			{
				dp[i][j]=max({dp[i][j-1],dp[i-1][j],dp[i-1][j-1]+(t1[i]==t2[j])});
			}
		}
		cout<<dp[e-b+1][y-x+1]<<"\n";
	}
}