【每日一题】合并回文子串
合并回文子串
https://ac.nowcoder.com/acm/problem/13230
题目
题目描述：输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。
我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。
需要求出所有可能的C中价值最大的字符串，输出这个最大价值即可。
第一行一个整数T(T ≤ 50)。
接下来2T行，每两行两个字符串分别代表A,B(|A|,|B| ≤ 50)，A,B的字符集为全体小写字母。
对于每组数据输出一行一个整数表示价值最大的C的价值。
解析
这道题是一个字符串dp。
- 我们知道，字符串dp一般用dp[i][j]来表示 i 与 j 之间的最大回文串值。
这道题的思路是怎么来的呢？
- 这道题首先不难发现，是有两个字符串组成的。
- 然后根据我们一般的思想，我们要求 i 和 j 之间的回文串值，但是由于我们在探索的过程中只要知道这个区间是不是回文串就行了。
- 接下来就是邓老师教给我的迷惑行为了，我们列举出一个四维数组，每两个为一组表示出两个回文串的首尾。并依照次判断这个区间是不是回文串。
- 根据递推的思想：我们从0开始加长回文串，所以我们判断是否为回文串只要判断：某一个已知的回文串，同时新增的最外层的一对是否相等的就行了。
- 所以我们可以得到递推公式：
f[l1][r1][l2][r2] |= f[l1 + 1][r1 - 1][l2][r2]; f[l1][r1][l2][r2] |= f[l1 + 1][r1][l2][r2 - 1]; f[l1][r1][l2][r2] |= f[l1][r1 - 1][l2 + 1][r2]; f[l1][r1][l2][r2] |= f[l1][r1][l2 + 1][r2 - 1]; //左边均为已知串，是否是回文串根据值为0/1来决定 //此处用或运算表示两者都要成立，答案为1。右边分别为四种情况
为什么又四种情况呢？因为我们有两个字符串，所以有两个头两个尾，但是不能确定谁在前谁在后：所以2 x 2就是四种了。 - 递推出来了我们就可以遍历了，四层循环是我万万没想到的。
打代码：
- 打代码就是两步，输入+四层循环遍历所有情况。套出最大值就行了
AC代码
#include <iostream>
#include <cstring>
using namespace std;
#define js ios::sync_with_stdio(false);
//代码预处理区
const int MAX = 50 + 7;
int f[MAX][MAX][MAX][MAX];
char s1[MAX], s2[MAX];
//全局变量区
int main() {
js;
int t; cin >> t;
while (t--) {
memset(f, 0, sizeof(f));
cin >> s1 + 1 >> s2 + 1;
int len1 = strlen(s1 + 1), len2 = strlen(s2 + 1), ans = 0;
for (int i = 0; i <= len1; i++)
for (int j = 0; j <= len2; j++)
for (int l1 = 1, r1 = l1 + i - 1; r1 <= len1; l1++, r1++)
for (int l2 = 1, r2 = l2 + j - 1; r2 <= len2; l2++, r2++) {
if (i + j <= 1) f[l1][r1][l2][r2] = 1;
else {
if (s1[l1] == s1[r1] && r1 > 0)
f[l1][r1][l2][r2] |= f[l1 + 1][r1 - 1][l2][r2];
if (s1[l1] == s2[r2] && r2 > 0)
f[l1][r1][l2][r2] |= f[l1 + 1][r1][l2][r2 - 1];
if (s2[l2] == s1[r1] && r1 > 0)
f[l1][r1][l2][r2] |= f[l1][r1 - 1][l2 + 1][r2];
if (s2[l2] == s2[r2] && r2 > 0)
f[l1][r1][l2][r2] |= f[l1][r1][l2 + 1][r2 - 1];
}
if (f[l1][r1][l2][r2]) ans = max(ans, r1 - l1 + r2 - l2 + 2);
}
cout << ans << endl;
}
return 0;
}
//函数区每日一题 文章被收录于专栏
憨憨的专栏
投递中移(苏州)软件技术有限公司等公司10个岗位 >
