#P18205. A Simple String Problem

A Simple String Problem

A Simple String Problem

有一个 22 行 nn 列的字符表格,每个单元格包含一个小写英文字母。你可以从任意单元格出发,走若干步,每一步只能向右或向下,最后停在任意单元格。按经过顺序拼接所有访问的字符,得到一个字符串。起点和终点的字符都计入;向下走时,同一列的上下两个字符都要计入。

当且仅当存在一个非空字符串 TT,使得 S=TTS=TT 时,称 SS 为双重串。例如 aa 和 xyzxyz 是双重串,a 和 xyzyz 不是。

求能够沿上述路径得到的最长双重串的长度。路径可以完全在同一行内。

输入格式

第一行一个整数 nn(1≤n≤2×1051\le n\le 2\times10^5)。

接下来两行,各有一个长度为 nn、只含小写英文字母的字符串,依次表示上行和下行。

本题输入只有一组数据。

输出格式

输出一个整数,表示最长双重串的长度。如果不能得到双重串,输出 00。

样例 1

输入:

5
abcab
acabc

输出:

6

样例 2

输入:

6
babbaa
babaaa

输出:

6

样例 3

输入:

2
ne
fu

输出:

0

样例说明

第一组样例的一种最优路径如下。图中下划线标记路径使用的字符:先经过上行第 11 至 33 列的 abc,再向下走到下行第 33 列,经过下行第 33 至 55 列的 abc,得到 abcabc,长度为 66。最优路径可能不唯一。

原题样例中的路径标记