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
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=2105;
const int INF = 100000000;
int f[maxn][maxn][4];
char a[maxn],b[maxn];
bool pd(int l,int r,int len){
    for(int i=0;i<len;i++)
        if(a[l+i]!=b[r+i])return 0;
    return 1;
}
int main(){
    scanf("%s",a+1);
    scanf("%s",b+1);
    int n=strlen(a+1),m=strlen(b+1);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)
            for(int k=0;k<=3;k++)f[i][j][k]=-INF;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=m;j++)f[i][j][3]=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j][3]=max(f[i-1][j-1][3],max(f[i-1][j][3],f[i][j-1][3]));
            if(i-1>=0&&j-1>=0&&pd(i,j,1)){
                f[i][j][1]=max(f[i][j][1],f[i-1][j-1][3]+1);
                f[i][j][3]=max(f[i][j][3],f[i-1][j-1][2]+1);
            }
            if(i-2>=0&&j-2>=0&&pd(i-1,j-1,2)){
                f[i][j][2]=max(f[i][j][2],f[i-2][j-2][3]+2);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX