题解 | #合并回文子串#

#include <iostream>
#include <cstring>
using namespace std;
const int N = 55;
const int M = 110;
int n;
char a[N];
char b[N];
int dp[N][N][N][N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a + 1 >> b + 1;
        int lena = strlen(a + 1);
        int lenb = strlen(b + 1);
        //printf("lena = %d, lenb = %d\n", lena, lenb);
        memset(dp, 0, sizeof(dp));
        int ans = 0;
        // 字符串a区间长度
        for (int len1 = 0; len1 <= lena; len1 ++) {
            // 字符串b区间长度
            for (int len2 = 0; len2 <= lenb; len2 ++) {
                // 字符串a的左右区间
                for (int l1 = 1, r1 = l1 + len1 - 1; l1 + len1 - 1 <= lena; l1++, r1++) {
                    // 字符串b的左右区间
                    for (int l2 = 1, r2 = l2 + len2 - 1; l2 + len2 - 1 <= lenb; l2++, r2++) {
                        bool f = false;
                        if(len1+len2<=1) f = true;
                        if(a[l1]==a[r1] && dp[l1+1][r1-1][l2][r2])
                            f = true;
                        if(a[l1]==b[r2] && dp[l1+1][r1][l2][r2-1])
                            f = true;
                        if(b[l2]==b[r2] && dp[l1][r1][l2+1][r2-1])
                            f = true;
                        if(a[r1]==b[l2] && dp[l1][r1-1][l2+1][r2])
                            f = true;
                        dp[l1][r1][l2][r2] = f;
                        if(f)
                            ans = max(ans ,len1+len2);
                            
                    }

                    
                }

            }
        }
        cout << ans << endl;
    }



    return 0;
}
// 64 位输出请用 printf("%lld")