8755: BZOJ4755:[Jsoi2016]扭动的回文串

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

JYY有两个长度均为N的字符串A和B。 一个“扭动字符串S(i,j,k)由A中的第i个字符到第j个字符组成的子串 与B中的第j个字符到第k个字符组成的子串拼接而成。 比如,若A=’XYZ’,B=’UVW’,则扭动字符串S(1,2,3)=’XYVW’。 JYY定义一个“扭动的回文串”为如下情况中的一个: 1.A中的一个回文串; 2.B中的一个回文串; 3.或者某一个回文的扭动字符串S(i,j,k) 现在JYY希望找出最长的扭动回文串。


输入格式

第一行包含一个正整数N。 第二行包含一个长度为N的由大写字母组成的字符串A。 第三行包含一个长度为N的由大写字母组成的字符串B。 1≤N≤10^5。


输出格式

输出的第一行一个整数,表示最长的扭动回文串。


样例输入

5
ABCDE
BAECB

样例输出

5
最佳方案中的扭动回文串如下所示(不在回文串中的字符用.表示):
.BC..
..ECB

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: