题解 | #合并回文子串#

import java.util.Scanner;

public class Test6 {
    static boolean[][][][] dp;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            String a = scanner.next();
            String b = scanner.next();
            int na = a.length();
            int nb = b.length();
            dp = new boolean[100][100][100][100];
            int ans = 1;
            a = "#" + a;
            b = "#" + b;
            for (int lena = 0; lena <= na; ++lena) {
                for (int lenb = 0; lenb <= nb; ++lenb) {
                    for (int la = 1, ra = la + lena - 1; ra <= na; ++la, ++ra) {
                        for (int lb = 1, rb = lb + lenb - 1; rb <= nb; ++lb, ++rb) {
                            if (lena + lenb <= 1) {
                                dp[la][ra][lb][rb] = true;
                            } else {
                                dp[la][ra][lb][rb] = false;
                                if (lena > 1 && a.charAt(la) == a.charAt(ra)) {
                                    dp[la][ra][lb][rb] |= dp[la + 1][ra - 1][lb][rb];
                                }
                                if (lenb > 1 && b.charAt(lb) == b.charAt(rb)) {
                                    dp[la][ra][lb][rb] |= dp[la][ra][lb + 1][rb - 1];
                                }
                                if (lena != 0 && lenb != 0 && a.charAt(la) == b.charAt(rb)) {
                                    dp[la][ra][lb][rb] |= dp[la + 1][ra][lb][rb - 1];
                                }
                                if (lena != 0 && lenb != 0 && b.charAt(lb) == a.charAt(ra)) {
                                    dp[la][ra][lb][rb] |= dp[la][ra - 1][lb + 1][rb];
                                }
                            }
                            if (dp[la][ra][lb][rb]) {
                                ans = Math.max(ans, lena + lenb);
                            }
                        }
                    }
                }
            }
            System.out.println(ans);
        }
    }
}