#P18205. A Simple String Problem
A Simple String Problem
A Simple String Problem
有一个 行 列的字符表格,每个单元格包含一个小写英文字母。你可以从任意单元格出发,走若干步,每一步只能向右或向下,最后停在任意单元格。按经过顺序拼接所有访问的字符,得到一个字符串。起点和终点的字符都计入;向下走时,同一列的上下两个字符都要计入。
当且仅当存在一个非空字符串 ,使得 时,称 为双重串。例如 aa 和 xyzxyz 是双重串,a 和 xyzyz 不是。
求能够沿上述路径得到的最长双重串的长度。路径可以完全在同一行内。
输入格式
第一行一个整数 ()。
接下来两行,各有一个长度为 、只含小写英文字母的字符串,依次表示上行和下行。
本题输入只有一组数据。
输出格式
输出一个整数,表示最长双重串的长度。如果不能得到双重串,输出 。
样例 1
输入:
5
abcab
acabc
输出:
6
样例 2
输入:
6
babbaa
babaaa
输出:
6
样例 3
输入:
2
ne
fu
输出:
0
样例说明
第一组样例的一种最优路径如下。图中下划线标记路径使用的字符:先经过上行第 至 列的 abc,再向下走到下行第 列,经过下行第 至 列的 abc,得到 abcabc,长度为 。最优路径可能不唯一。
