首页 > 试题广场 >

最长回文

[编程题]最长回文

时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

有两个长度均为n的字符串A和B。可以从A中选一个可以为空的子串A[l1..r1]，B中选一个可以为空的子串B[l2..r2]，满足r1=l2，然后把它们拼起来（A[l1..r1]+B[l2..r2]）。求用这样的方法能得到的最长回文串的长度。注意：求的不是本质不同的回文串个数哦！！！

输入描述:

第一行一个数n
第二行表示字符串A
第三行表示字符串B

输出描述:

输出一行一个数表示答案

示例1

输入

5
ZQZFC
NSZXL

输出

说明

A[1..3]=“ZQZ”，为一个长为3的回文串，B空

示例2

输入

7
NSZQZFC
CFZQZSN

输出

说明

A[1..4]=”NSZQ”
B[4..7]=”QZSN”
拼起来是”NSZQQZSN”，为一个长为8的回文串

备注:

对于100%的数据，有1 <= n <= 100000 , 字符全是大写英语字符

算法知识视频讲解

buerdepepeqi

发表于 2019-08-07 21:38:04

传送门:https://ac.nowcoder.com/acm/problem/14894题意：从字符串A中选出[l1,r1]的一段和字符串B中选出[l2,r2]的一段，使得 r1=l2，并且两端字符串拼接起来是回文串，求最长回文串长度题解:对字符串A和字符串B各自进行一次manacher，求出p数展开全文