题解 | #合并回文子串#

#include <iostream>
#include <cstring>
using namespace std;
//将满足条件的字串赋值为1，否则为0
//全局变量，系统统一初始化为全0
int dp[55][55][55][55];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; 
    cin >> t;
    string a,b;
    while(t--)
    {
        cin >> a >> b;
        memset(dp,0,sizeof dp);
        int res=0;
        //前两层循环控制两者的循环长度
        for(int len1 = 0;len1 <= a.size();len1++)
        for(int len2 = 0;len2 <= b.size();len2++)
        //后两层循环控制字串的始末位置
        for(int i = 1,j = i + len1 - 1;j <= a.size();i++,j++)
        for(int k = 1,l = k + len2 - 1;l <= b.size();k++,l++){
            //只有一个字符时，最小值为1
            if(j + l - k - i + 2 <= 1) dp[i][j][k][l] = 1;
            else{
                //下列需保证a[i - 1]到a[j - 1]是回文串
                //b[k - 1]到b[l - 1]是回文串
                //然后进行两者的组合（可能为AB形式，也可能为BA形式），进行赋值
                //采用“或”的形式，防止本来是回文串的字串被赋值为0
                if(a[i - 1]==a[j - 1])
                    dp[i][j][k][l] = dp[i][j][k][l] | dp[i + 1][j - 1][k][l];
                if(a[i - 1]==b[l - 1])
                    dp[i][j][k][l] = dp[i][j][k][l] | dp[i + 1][j][k][l - 1];
                if(b[k - 1]==a[j - 1])
                    dp[i][j][k][l] = dp[i][j][k][l] | dp[i][j - 1][k + 1][l];
                if(b[k - 1]==b[l - 1])
                    dp[i][j][k][l] = dp[i][j][k][l] | dp[i][j][k + 1][l - 1];
            }
            //当组合结束时，满足回文串时，求解最大值
            if(dp[i][j][k][l]) res = max(res,len1 + len2);
        }
        cout << res << endl;
    }
}