#P4755. [Jsoi2016]扭动的回文串

    ID: 3875 传统题 1000ms 512MiB 尝试: 590 已通过: 191 难度: 8 上传者: 标签>难度分类提高+/省选-字符串Manacher动态规划有限候选集缩减后缀数组排序与序列处理倍增计数排序Kasai 算法LCP+RMQ数据结构普通线段树CF2500

[Jsoi2016]扭动的回文串

[JSOI2016] 扭动的回文串

题目描述

JYY 有两个长度均为 NN 的字符串 A,BA,B。

对于 1≤i≤j≤k≤N1\le i\le j\le k\le N,把子串 AiAi+1…AjA_iA_{i+1}\ldots A_j 与 BjBj+1…BkB_jB_{j+1}\ldots B_k 拼接,得到扭动字符串 S(i,j,k)S(i,j,k)。两个子串都包含编号为 jj 的位置。例如,当 A=XYZA=\mathtt{XYZ}、B=UVWB=\mathtt{UVW} 时,S(1,2,3)=XYVWS(1,2,3)=\mathtt{XYVW}。

扭动的回文串可以是 AA 或 BB 中的一个回文子串,也可以是一个本身为回文串的 S(i,j,k)S(i,j,k)。求其中最大的长度。

输入格式

第一行包含一个正整数 NN。

第二、三行分别包含长度为 NN 的字符串 A,BA,B,均只由大写英文字母组成。

输出格式

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

样例 #1

样例输入 #1

5
ABCDE
BAECB

样例输出 #1

5

样例说明

选择 S(2,3,5)S(2,3,5),得到回文串 BCECB\mathtt{BCECB}。下方用点表示没有选入的字符。

.BC..
..ECB

数据范围

1≤N≤1051\le N\le10^5。