题解 | 合并回文子串

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 55;
int dp[MAXN][MAXN][MAXN][MAXN];

int main() {
    int t;
    cin >> t;
    while (t--) {
        string a, b;
        cin >> a >> b;
        memset(dp, 0, sizeof(dp));
        int maxn = 0;
        const int n = a.size(), m = b.size();

        // 提前初始化所有 Alen + Blen <= 1 的情况
        // 情况1：Alen=0, Blen=0（空字符串）
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                dp[i][i][j][j] = 1;  // 空字符串是回文
                maxn = max(maxn, 0); // 更新最大长度
            }
        }

        // 情况2：Alen=1, Blen=0（A中取1字符）
        for (int i = 0; i < n; i++) { // i范围[0,n-1]
            for (int j = 0; j <= m; j++) {
                dp[i][i + 1][j][j] = 1; // 子串a[i..i]
                maxn = max(maxn, 1);
            }
        }

        // 情况3：Alen=0, Blen=1（B中取1字符）
        for (int j = 0; j < m; j++) { // j范围[0,m-1]
            for (int i = 0; i <= n; i++) {
                dp[i][i][j][j + 1] = 1; // 子串b[j..j]
                maxn = max(maxn, 1);
            }
        }

        // 主循环处理 Alen + Blen >= 2 的情况
        for (int Alen = 0; Alen <= n; Alen++) {
            for (int Blen = 0; Blen <= m; Blen++) {
                if (Alen + Blen < 2) continue; // 跳过已初始化的情况

                for (int i = 0; i + Alen <= n; i++) {
                    int endA = i + Alen;
                    for (int j = 0; j + Blen <= m; j++) {
                        int endB = j + Blen;

                        // 状态转移（无需再判断 Alen+Blen<=1）
                        if (Alen >= 2 && a[i] == a[endA - 1])
                            dp[i][endA][j][endB] = max(dp[i][endA][j][endB],
                                                       dp[i + 1][endA - 1][j][endB]);

                        if (Blen >= 2 && b[j] == b[endB - 1])
                            dp[i][endA][j][endB] = max(dp[i][endA][j][endB],
                                                       dp[i][endA][j + 1][endB - 1]);

                        if (Alen >= 1 && Blen >= 1 && a[i] == b[endB - 1])
                            dp[i][endA][j][endB] = max(dp[i][endA][j][endB],
                                                       dp[i + 1][endA][j][endB - 1]);

                        if (Alen >= 1 && Blen >= 1 && a[endA - 1] == b[j])
                            dp[i][endA][j][endB] = max(dp[i][endA][j][endB],
                                                       dp[i][endA - 1][j + 1][endB]);

                        if (dp[i][endA][j][endB])
                            maxn = max(maxn, Alen + Blen);
                    }
                }
            }
        }
        cout << maxn << endl;
    }
    return 0;
}