A6320. 「JSOI2016」扭动的回文串
编程题
省选/NOI-
知识点
题目描述
JYY 有两个长度均为 $N$ 的字符串 $A$ 和 $B$。
一个「扭动字符串」$S(i,j,k)$ 由 $A$ 中的第 $i$ 个字符到第 $j$ 个字符组成的子串与 $B$ 中的第 $j$ 个字符到第 $k$ 个字符组成的子串拼接而成。
比如，若 $A=$’`
JYY 定义一个「扭动的回文串」为如下情况中的一个：
1. $A$ 中的一个回文串；
2. $B$ 中的一个回文串；
3. 或者某一个回文的扭动字符串$S(i,j,k)$
现在 JYY 希望找出最长的扭动回文串。
一个「扭动字符串」$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$。
第二行包含一个长度为 $N$ 的由大写字母组成的字符串 $A$。
第三行包含一个长度为 $N$ 的由大写字母组成的字符串 $B$。
输出格式
输出的第一行一个整数，表示最长的扭动回文串。
输入输出样例
输入 #1
5 ABCDE BAECB
输出 #1
5
说明/提示
对于所有的数据，$1 \leq N \leq 10^5$。