A22694.扭动的回文串

省选/NOI-

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

JYY 有两个长度均为 NN 的字符串 AABB

一个扭动字符串 S(i,j,k)S(i,j,k)AA 中的第 ii 个字符到第 jj 个字符组成的子串与 BB 中的第 jj 个字符到第 kk 个字符组成的子串拼接而成。

比如,若 A=XYZA= \mathtt{XYZ}B=UVWB= \mathtt{UVW},则扭动字符串 S(1,2,3)=XYVWS(1,2,3)=\mathtt{XYVW}

JYY 定义一个扭动的回文串为如下情况中的一个:

  1. AA 中的一个回文串;
  2. BB 中的一个回文串;
  3. 或者某一个回文的扭动字符串 S(i,j,k)S(i,j,k)

现在 JYY 希望找出最长的扭动回文串。

输入格式

第一行包含一个正整数 NN
第二行包含一个长度为 NN 的由大写字母组成的字符串 AA
第三行包含一个长度为 NN 的由大写字母组成的字符串 BB

输出格式

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

输入输出样例

  • 输入#1

    5
    ABCDE
    BAECB

    输出#1

    5

说明/提示

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

.BC..
..ECB

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

首页