14. God and Gods

单点时限: 2.0 sec

内存限制: 256 MB

起初,世界上没有题,没有做题的人。

第一天,上帝说,要有 AGCT,于是就有了 AGCT。

第二天,上帝说,要有题,然后就有了一道有关 AGCT 的题。

第三天,上帝喊来了众神,让他们创造两个只含有 AGCT 的字符串,于是众神们就创造了两个字符串。

第四天,上帝说,这两个字符串既要相等,又要是正回文串(字符串倒置后与本身相等,且长度为奇数),要让众神重新造。众神有点不悦,他们决定从原先的两个字符串中分别找出一个连续子串。

第五天,上帝说,这个子串要尽量长。众神皆勃然大怒,拂袖而去,留下你在这做题。

输入格式

两行。

每一行分别由一个数 (n) ((1 \leq n \leq 10^5)) 开头,然后是一个长度为 (n) 的字符串,仅有大写英文字母 A, G, C, T 组成。

对于约 40% 的数据,有 (n \leq 10^3)。

输出格式

输出一个整数:最长的公共正回文子串的长度。

样例

Input
12 AGCGCGATTTTT
14 ATTTTTTACGCGCA
Output
5
Input
10 AGCGATTTTT
11 ATTTTTTACGCA
Output
5
Input
10 ACGATCGGAT
13 AGCGATGCGTACG
Output
1

2 人解决,32 人已尝试。

6 份提交通过,共有 200 份提交。

9.9 EMB 奖励。

创建: 7 年,7 月前.

修改: 7 年,2 月前.

最后提交: 2 月,3 周前.

来源: 蓝桥杯 2015 改编

题目标签