题目的主要信息：

• 两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变
• 需求出所有可能的串C中的最长回文子串的长度

具体做法：

这是一个区间DP问题。我们用$dp[l1][r1][l2][r2]dp[l1][r1][l2][r2]$表示字符串A在区间$[l1,r1][l1,r1]$和字符串B在区间$[l2,r2][l2,r2]$合并后能否构成回文子串。

状态转移有四种情况：

1. A[l1]=A[r2]，即字符串A的区间首等于区间尾，我们在字符串A在区间$[l1+1,r1-1][l1+1,r1-1]$和字符串B在区间$[l2,r2][l2,r2]$合并后的字符串首尾分别加上这个字符即可，则：$dp[l1][r1][l2][r2]\mathrm{\mid }=dp[l1+1][r1-1][l2][r2]dp[l1][r1][l2][r2]\; |=\; dp[l1\; +\; 1][r1\; -\; 1][l2][r2]$

2. A[l1]=B[r2]，即字符串A的区间首等于字符串B的区间尾，我们在字符串A在区间$[l1+1,r1][l1+1,r1]$和字符串B在区间$[l2,r2-1][l2,r2-1]$合并后的字符串首尾分别加上这个字符即可，则：$dp[l1][r1][l2][r2]\mathrm{\mid }=dp[l1+1][r1][l2][r2-1]dp[l1][r1][l2][r2]\; |=\; dp[l1\; +\; 1][r1][l2][r2\; -\; 1]$

3. A[r1]=B[l2]，即字符串A的区间尾等于字符串B的区间首，我们在字符串A在区间$[l1,r1-1][l1,r1-1]$和字符串B在区间$[l2+1,r2][l2+1,r2]$合并后的字符串首尾分别加上这个字符即可，则：$dp[l1][r1][l2][r2]\mathrm{\mid }=dp[l1][r1-1][l2+1][r2]dp[l1][r1][l2][r2]\; |=\; dp[l1][r1\; -\; 1][l2\; +\; 1][r2]$

4. B[l2]=B[r2]，即字符串B的区间尾等于字符串B的区间首，我们在字符串A在区间$[l1,r1][l1,r1]$和字符串B在区间$[l2+1,r2-1][l2+1,r2-1]$合并后的字符串首尾分别加上这个字符即可，则：$dp[l1][r1][l2][r2]\mathrm{\mid }=dp[l1][r1][l2+1][r2-1]dp[l1][r1][l2][r2]\; |=\; dp[l1][r1][l2\; +\; 1][r2\; -\; 1]$

我们只要遍历两个字符串的长度，枚举每个区间的首尾，对是回文的统计长度，更新最长记录即可。

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;

int main() {
	int T;
	cin >> T;
	int dp[52][52][52][52];
	while (T--) {
		string A, B;
		cin >> A >> B;
		int n = A.length();
		int m = B.length();
        A = " " + A; //从下标1开始
        B = " " + B;
		int res = 0;
		memset(dp, 0, sizeof dp);  //dp数组初始化为0
		for (int i = 0; i <= n; i++) {  //枚举字符串A的长度
			for (int j = 0; j <= m; j++) { //枚举字符串B的长度
				for (int l1 = 1; l1 + i - 1 <= n; l1++) { //枚举字符串A的左边界
					for (int l2 = 1; l2 + j - 1 <= m; l2++) { // 枚举字符串B的左边界
						int r1 = i + l1 - 1; //字符串A的右边界
						int r2 = j + l2 - 1; //字符串B的右边界
						if (i + j <= 1)
							dp[l1][r1][l2][r2] = 1;///初始化
						else {//四种状态转移
							if (i > 1 && A[l1] == A[r1])
								dp[l1][r1][l2][r2] |= dp[l1 + 1][r1 - 1][l2][r2];
							if (i && j && A[l1] == B[r2])
								dp[l1][r1][l2][r2] |= dp[l1 + 1][r1][l2][r2 - 1];
							if (i && j && A[r1] == B[l2])
								dp[l1][r1][l2][r2] |= dp[l1][r1 - 1][l2 + 1][r2];
							if (j > 1 && B[l2] == B[r2])
								dp[l1][r1][l2][r2] |= dp[l1][r1][l2 + 1][r2 - 1];
						}
						if (dp[l1][r1][l2][r2]) //如果这区间为1则是回文
							res = max(res, i + j);
					}
				}
			}
		}
		cout << res << endl;
	}
	return 0;
}

复杂度分析：

• 时间复杂度：$O(n^2{m}^2)O(n^2m^2)$，其中$nn$与$mm$分别为两个字符串的长度，四层遍历循环
• 空间复杂度：$O(n^2{m}^2)O(n^2m^2)$，辅助数组dp的空间