单点时限: 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)。
输出一个整数:最长的公共正回文子串的长度。
12 AGCGCGATTTTT 14 ATTTTTTACGCGCA
5
10 AGCGATTTTT 11 ATTTTTTACGCA
5
10 ACGATCGGAT 13 AGCGATGCGTACG
1