链接：https://ac.nowcoder.com/acm/problem/13230
来源：牛客网
题目描述
输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可
输入描述:
第一行一个整数T(T ≤ 50)。 接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。
输出描述:
对于每组数据输出一行一个整数表示价值最大的C的价值。
示例1
输入
2 aa bb a aaaabcaa
输出
4 5
析：这是一个区间DP，这个容易看出来，状态表示为dp[i][j][k][l]表示第一个字符串 i~j 的子串与第二个字符串的 k~j 子串能不能组成回文串，看到这，应该就知道该怎么做了。
假设第一个字符串为s1，第二个字符串为s2，状态转移方程如下：
if s1[i] == s1[j]: dp[i][j][k][l] |= dp[i+1][j-1][k][l]
if s1[i] == s2[l]: dp[i][j][k][l] |= dp[i+1][j][k][l-1]
if s1[j] == s2[k]: dp[i][j][k][l] |= dp[i][j-1][k+1][l]
if s2[k] == s2[l]: dp[i][j][k][l] |= dp[i][j][k+1][l-1]
代码如下：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <cstring>
#include <set>
#include <queue>
#include <algorithm>
#include <vector>
#include <map>
#include <cctype>
#include <cmath>
#include <stack>
#include <sstream>
#include <list>
#include <assert.h>
#include <bitset>
#include <numeric>
#define debug() puts("++++")
#define gcd(a, b) __gcd(a, b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define fi first
#define se second
#define pb push_back
#define sqr(x) ((x)*(x))
#define ms(a,b) memset(a, b, sizeof a)
#define sz size()
#define be begin()
#define ed end()
#define pu push_up
#define pd push_down
#define cl clear()
#define lowbit(x) -x&x
#define all 1,n,1
#define FOR(i,n,x) for(int i = (x); i < (n); ++i)
#define freopenr freopen("in.in", "r", stdin)
#define freopenw freopen("out.out", "w", stdout)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const LL LNF = 1e17;
const double inf = 1e20;
const double PI = acos(-1.0);
const double eps = 1e-8;
const int maxn = 50 + 7;
const int maxm = 2000000 + 7;
const LL mod = 1e9 + 7;
const int dr[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dc[] = {0, 0, 1, -1, 1, -1, 1, -1};
int n, m;
inline bool is_in(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < m;
}
bool dp[maxn][maxn][maxn][maxn];
bool f[maxn][maxn];
bool g[maxn][maxn];
int main(){
int T; cin >> T;
while(T--){
ms(dp, 0); ms(f, 0); ms(g, 0);
string s1, s2; cin >> s1 >> s2;
n = s1.sz, m = s2.sz;
int res = 1;
for(int i = n; i >= 1; --i)
for(int j = i; j <= n; ++j)
if(s1[i-1] == s1[j-1]) f[i][j] = f[i+1][j-1] || i+1 >= j-1;
for(int i = m; i >= 1; --i)
for(int j = i; j <= m; ++j)
if(s2[i-1] == s2[j-1]) g[i][j] = g[i+1][j-1] || i+1 >= j-1;
for(int i = n; i >= 1; --i)
for(int j = i; j <= n; ++j)
for(int k = m; k >= 1; --k)
for(int l = k; l <= m; ++l){
bool &ans = dp[i][j][k][l];
if(i == j && k == l){
if(s1[i-1] == s2[k-1]) ans = true;
}
else if(i == j){
if(s1[i-1] == s2[k-1] && g[k+1][l] || s1[i-1] == s2[l-1] && g[k][l-1]) ans = true;
if(s2[l-1] == s2[k-1]) ans |= k + 1 == l || dp[i][j][k+1][l-1];
}
else if(k == l){
if(s2[k-1] == s1[i-1] && f[i+1][j] || s2[k-1] == s1[j-1] && f[i][j-1]) ans = true;
if(s1[i-1] == s1[j-1]) ans |= dp[i+1][j-1][k][l] || i + 1 == j;
}
if(i == j || k == l){
if(ans) res = max(res, j+l-k-i+2);
continue;
}
if(s1[i-1] == s1[j-1]) ans |= dp[i+1][j-1][k][l] || (i+1 == j && g[k][l]);
if(s1[i-1] == s2[l-1]) ans |= dp[i+1][j][k][l-1] || !(i+1 <= j && k <= l-1) || (i+1 > j && g[k][l-1]) || (k > l-1 && f[i+1][j]);
if(s2[k-1] == s1[j-1]) ans |= dp[i][j-1][k+1][l] || !(i <= j-1 && k+1 <= l) || (i > j-1 && g[k+1][l]) || (k+1 > l && f[i][j-1]);
if(s2[k-1] == s2[l-1]) ans |= dp[i][j][k+1][l-1] || (k+1 == l && f[i][j]);
if(ans) res = max(res, j+l-k-i+2);
}
cout << res << endl;
}
return 0;
}
合并回文子串