首页 > 试题广场 >

合并回文子串

[编程题]合并回文子串
  • 热度指数：1068 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入两个字符串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的价值。
示例1

输入

2
aa
bb
a
aaaabcaa

输出

4
5
算法知识视频讲解
开通博客
头像 shyyhs
发表于 2020-03-26 03:09:01
粗体内容 说句实话我的能力还停留在那种二维线性/区间dp上...所以做这个题真的有点吃力，不过这个题的转态转移方程还是比较好推.我推了方程到我看别人提交的代码,我浪费了6h...第一次推出方程写不出题,,,怎么说 尽量自己想...就是这个心态,我推出方程后不会处理...一直输出别的数或者啥玩意的, 展开全文
去ta的博客 赞 (18) 回复(3) 收起
头像 LB_tq
发表于 2020-03-25 12:58:57
Solution 看到数据范围可以想到区间。 由题意可知字串是连续的。设 为在 中选取 到 ，在 中选取 到 是否能构成回文串。转移方程如下： （，) （，) （，，) （，，） 利用或运算可以方便的转移。当两个字符串最多选出一个字符时，此时显然有 ，作为边界条件。 时间复 展开全文
去ta的博客 赞 (14) 回复(3) 收起
头像 吴国庆
发表于 2020-03-25 15:39:07
题意 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能的C中价值最大的 展开全文
去ta的博客 赞 (10) 回复(0) 收起
头像 一只橘橘猫
发表于 2020-03-26 09:31:09
涉及知识点： 区间dp solution： 划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。 大多数区间dp的模板都长这样子： for(int len = 1; len <= n; len++){ f 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 工大最菜
发表于 2020-03-25 16:13:57
思路：我们用f[l1][r1][l2][r2]:表示A[l1] ~ A[r1]和B[l2] ~ B[r2]是否能合并成一个回文串。考虑转移：因为顺序是不能改变的。所以只有这4个可能的转移。 #include <bits/stdc++.h> using namespace std; #d 展开全文
去ta的博客 赞 (5) 回复(1) 收起
头像 与人无语
发表于 2020-05-05 13:49:58
这是一道区间dp的题我们设置这样一个数组 dp[l1][r1][l2][r2] 来代表字符串 s1 s2 选择的范围那么递推方程怎么来 对于这样一个方程 它只能由这四种情况得来dp[l1+1][r1][l2][r2-1] dp[l1+1][r1-1][l2][r2]dp[l1][r1][l2 展开全文
去ta的博客 赞 (4) 回复(4) 收起
头像 人丑心更黑
发表于 2021-01-20 14:11:03
今天做的是合并回文子串虽说看到题目就知道是个dp，无奈写不出来。 首先来看题意：给两个字符串A和B，现在将A和B进行合并，要求两个字符串中原有的相对位置不发生变化，问合并的可能中最长的回文子串长度？这里A和B的长度都不超过50. 题目类型：区间DP 题解已经讲的很好了，这里做个总结： 1.最长回文 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 get_right_Lkl
发表于 2020-03-25 22:33:05
题目描述： 输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。 我们定义字符串的价值为其最长回文子串的长度（回文串表示从正反两边看完全一致的字符串，如"aba"和"xyyx"）。需要求出所有可能的C中价 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 平凡的小白
发表于 2020-09-28 00:24:28
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+7; typedef long long ll; inline ll read(){ ll s = 0, w = 1; char ch = getch 展开全文
去ta的博客 赞 (2) 回复(2) 收起
头像 Kur1su
发表于 2020-03-26 10:24:00
链接：https://ac.nowcoder.com/acm/problem/13230来源：牛客网 题目描述输入两个字符串A和B，合并成一个串C，属于A和B的字符在C中顺序保持不变。如"abc"和"xyz"可以被组合成"axbycz"或"abxcyz"等。我们定义字符串的价值为其最长回文子串的长度 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

C++工程师 golang工程师 2017 iOS工程师 安卓工程师 运维工程师 区间dp 前端工程师 算法工程师 测试工程师 PHP工程师 c#工程师 美团 动态规划 测试开发工程师 大数据开发工程师 Java工程师
来自：CodeM 2017美...
难度：
4条回答 4561浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号