链接：https://ac.nowcoder.com/acm/problem/13230 来源：牛客网

输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。 需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可

做法

区间dp题，学到的一个点就是如果范围小就考虑开多维去存储，所以dp的思维就是两个串的左右端点，那么就有四种情况，当a串左右相等时，我们看一下缩小一点的a串是否是回文，b串相同，如果a串的开头和b串的结尾一样，考虑把b串字符插入a串，那么就需要看缩小一点，两个端点是否相同，那么a串结尾和b串开头类似，为什么没有a开头和b开头以及a结尾和b结尾？

因为我们是考虑一个区间内两个长度的串是否是回文，而这两种情况不能通过递推得到，其他四种情况，当头尾相同，我们可以考虑一直缩小字串看看是否是回文，而头头相同和尾尾相同并不能得到一个回文。（注意：每次操作数组需要情空，为了不用memset，于是每次先把当前串清为0）

#include<bits/stdc++.h>
#define endl "\n"
#define int long long
/*inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}*/
//dont forget to check long long
//别写重变量名
//记得判越界
//别死磕
//处理字符串删掉关流
//用__int128时记得删掉关流
int f[60][60][60][60];
void slove()
{
    //memset(f,0,sizeof(f));
    int ans=0;
    std::string a,b;
    std::cin>>a>>b;
    a=' '+a;
    b=' '+b;
    int n=a.length()-1;
    int m=b.length()-1;
    for(int len1=0;len1<=n;len1++)
    {
        for(int len2=0;len2<=m;len2++)
        {
            for(int i=1,j=len1+i-1;j<=n;i++,j++)
            {
                for(int l=1,r=len2+l-1;r<=m;l++,r++)
                {
                    if(len1+len2<=1) f[i][j][l][r]=1;
                    else
                    {
                        f[i][j][l][r]=0;
                        if(a[i]==a[j]&&len1>0)
                        {
                            if(f[i+1][j-1][l][r]) f[i][j][l][r]=1;
                        }
                        if(a[j]==b[l]&&len1>0&&len2>0)
                        {
                            if(f[i][j-1][l+1][r]) f[i][j][l][r]=1;
                        }
                        if(a[i]==b[r]&&len1>0&&len2>0)
                        {
                            if(f[i+1][j][l][r-1]) f[i][j][l][r]=1;
                        }
                        if(b[l]==b[r]&&len2>0) 
                        {
                            if(f[i][j][l+1][r-1]) f[i][j][l][r]=1;
                        }
                    }
                    if(f[i][j][l][r]) ans=std::max(ans,len1+len2);
                }
            }
        }
    }
     //std::cout<<a[n]<<' '<<b[m]<<endl;
    std::cout<<ans<<endl;
}
signed main()
{
    int T; 
    std::cin>>T;
    while(T--)    {
        slove();
    }

    return 0;
}

！！！！！！！为了从1下表开始可以在前面加一个空格，但最后一个元素的下标还是字符串长度-1，切记!!!!!