#2073. 「JSOI2016」扭动的回文串

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输出格式

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

样例

样例输入

5
ABCDE
BAECB

样例输出

5

样例解释

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

.BC..
..ECB

数据范围与提示

对于所有的数据, 1 \leq N \leq 10^5