四维dp

dp[i][j][k][l]代表A从0到i-1的子串的长度为k的后缀和B的从0到j-1的子串的长度为l的后缀是否能形成回文后缀。

递推式两种情况：

1. A[i-1]放在最后，遍历所有后缀组合看是否能形成回文后缀，如果A的后缀A[a~i-2]和B的后缀B[b~j-1]能形成回文并且A[a-1]和B[b-1]其中有一个与A[i-1]相同，那么就能用A[a-1~i-1]和B[b~j-1]或者A[a~i-1]和B[b-1~j-1]形成回文后缀了。

2. B[j-1]放在最后，与1同理。

#include<bits/stdc++.h>

#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())

const int mod = 1e9+7;
const int MAXN = 60;
using namespace std;


int main(){
    int n ;
    bool dp[MAXN][MAXN][MAXN][MAXN];
    cin >> n;
    for(int i = 0;i <n ;++i){
        string A, B;
        cin >> A >> B;
        int ans = 1;
        memset(dp, 0, sizeof dp);
        dp[0][0][0][0] = true;
        for(int j = 0; j <= A.size(); ++j)
            for(int k = 0; k <= B.size(); ++k){
                if(j == 0 && k == 0) continue;
                dp[j][k][0][0] = dp[j][k][1][0] = dp[j][k][0][1] = true;
                for(int a = 0; a <= j-1; ++a)//ends with A[j-1]
                    for(int b = 0; b <= k; ++b){
                        if(!dp[j-1][k][a][b]) continue;
                        if(j-1-a > 0 && A[j-2-a] == A[j-1]) dp[j][k][a+2][b] = true;
                        if(k-b>0 && B[k-b-1] == A[j-1]) dp[j][k][a+1][b+1] = true;
                        if(dp[j][k][a+1][b+1]||dp[j][k][a+2][b]) ans = max(ans, a+b+2);
                    }
                for(int a = 0; a <= j; ++a)//ends with B[k-1]
                    for(int b = 0; b <= k-1; ++b){
                        if(!dp[j][k-1][a][b]) continue;
                        if(j-a>0 && A[j-1-a] == B[k-1]) dp[j][k][a+1][b+1] = true; 
                        if(k-b-1> 0 && B[k-b-2] == B[k-1]) dp[j][k][a][b+2] = true;
                        if(dp[j][k][a+1][b+1]||dp[j][k][a][b+2]) ans = max(ans, a+b+2);
                    }
            }
        cout << ans << endl;
    }
    return 0;
}