题解 | 合并回文子串

史题，考虑dp[l1][r1][l2][r2] 维护“考虑了 A 串中从 l1 到 r1 部分，B 串从 l2 到 r2 部分，是否能构成回文串”，然后dp时分类讨论一下转移情况，当更新出新的合法dp值时，直接更新答案即可，时间复杂度 O(n^4)。

#include<bits/stdc++.h>
using i64 = long long;

bool dp[51][51][51][51];

bool sp[51][51];
bool tp[51][51];

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int t;
    std::cin >> t;
    while (t--) {
        std::string s, t;
        std::cin >> s >> t;

        int ans = 1;
        int n = s.size(), m = t.size();

        memset(dp, 0, sizeof dp);

        // 两边各取一个拼
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][i][j][j] = (s[i] == t[j]);
            }
        }
        // 预处理回文
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sp[i][j] = 1;
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                tp[i][j] = 1;
            }
        }

        // 暴力处理单独是不是回文串
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                bool ok = 1;
                for (int l = i, r = j; l < r; l++, r--) {
                    ok &= (s[l] == s[r]);
                }
                sp[i][j] = ok;
                if (ok) {
                    ans = std::max(ans, j - i + 1);
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = i; j < m; j++) {
                bool ok = 1;
                for (int l = i, r = j; l < r; l++, r--) {
                    ok &= (t[l] == t[r]);
                }
                tp[i][j] = ok;
                if (ok) {
                    ans = std::max(ans, j - i + 1);
                }
            }
        }

        // 处理一边只取一个字符的回文串
        for (int i = 0; i < n; i++) {
            for (int l2 = 1; l2 <= m; l2++) {
                for (int j = 0; j + l2 - 1 < m; j++) {
                    dp[i][i][j][j + l2 - 1] |= (s[i] == t[j + l2 - 1] && tp[j][j + l2 - 1 - 1]);
                    dp[i][i][j][j + l2 - 1] |= (s[i] == t[j] && tp[j + 1][j + l2 - 1]);

                    if (l2 == 2) {
                        dp[i][i][j][j + l2 - 1] |= (t[j] == t[j + l2 - 1] && tp[j + 1][j + l2 - 1 - 1]);
                    }
                    if (dp[i][i][j][j + l2 - 1]) {
                        ans = std::max(ans, l2 + 1);
                    }
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int l1 = 1; l1 <= n; l1++) {
                for (int j = 0; j + l1 - 1 < n; j++) {
                    dp[j][j + l1 - 1][i][i] |= (t[i] == s[j + l1 - 1] && sp[j][j + l1 - 1 - 1]);
                    dp[j][j + l1 - 1][i][i] |= (t[i] == s[j] && sp[j + 1][j + l1 - 1]);
                    if (l1 == 2) {
                        dp[j][j + l1 - 1][i][i] |= (s[j] == s[j + l1 - 1] && sp[j + 1][j + l1 - 1 - 1]);
                    }
                    if (dp[j][j + l1 - 1][i][i]) {
                        ans = std::max(ans, l1 + 1);
                    }
                }
            }
        }
        // 主dp部分
        for (int l1 = 1; l1 <= n; l1++) {
            for (int l2 = 1; l2 <= m; l2++) {
                for (int i = 0; i + l1 - 1 < n; i++) {
                    for (int j = 0; j + l2 - 1 < m; j++) {
                        if (l1 == 2) {// sc + st[] + sc
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= (s[i] == s[i + l1 - 1] && tp[j][j + l2 - 1]);
                        } else if (l1 > 2) {
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= ((s[i] == s[i + l1 - 1]) && dp[i + 1][i + l1 - 1 - 1][j][j + l2 - 1]);
                        }
                        if (l2 == 2) {// tc + st[] + tc
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= (t[j] == t[j + l2 - 1] && sp[i][i + l1 - 1]);
                        } else if (l2 > 2) {
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= ((t[j] == t[j + l2 - 1]) && dp[i][i + l1 - 1][j + 1][j + l2 - 1 - 1]);
                        }

                        if (l1 > 1 && l2 > 1) {
                            // sc + st[] + tc
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= ((s[i] == t[j + l2 - 1]) && dp[i + 1][i + l1 - 1][j][j + l2 - 1 - 1]);
                            // tc + st[] + sc
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= ((t[j] == s[i + l1 - 1]) && dp[i][i + l1 - 1 - 1][j + 1][j + l2 - 1]);
                        } else if (l1 == 1 && l2 >= 4) {// tc + ts[] + tc
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= ((t[j] == t[j + l2 - 1]) && dp[i][i + l1 - 1][j + 1][j + l2 - 1 - 1]);
                        } else if (l2 == 1 && l1 >= 4) {// sc + ts[] + sc
                            dp[i][i + l1 - 1][j][j + l2 - 1] |= ((s[i] == s[i + l1 - 1]) && dp[i + 1][i + l1 - 1 - 1][j][j + l2 - 1]);
                        }

                        
                        if (dp[i][i + l1 - 1][j][j + l2 - 1]) {
                            // if (l1 + l2 == 7) {
                            //     std::cout << i << ", " << i + l1 -1 << ", " << j << j + l2 - 1 << "]\n";
                            // }
                            ans = std::max(ans, l1 + l2);
                        }
                    }
                }
            }
        }

        std::cout << ans << "\n";
    }

    return 0;
}

https://www.nowcoder.com/discuss/727521113110073344