#PQJ119x6218. QOJ 119_6218
QOJ 119_6218
第三轮第二试 扭动的回文串 扭动的回文串 【故事背景】 JYY 在研究回文串的时候,偶然发现了一种有趣的“扭动回文串”。 【问题描述】 JYY 有两个长度均为N 的字符串A 和B。 一个“扭动字符串” 𝑆𝑖, 𝑗, 𝑘 由A 中的第i 个字符到第j 个字符组成的子串 与B 中的第j 个字符到第k 个字符组成的子串拼接而成。 比如,若A=’XYZ’,B=’UVW’,则扭动字符串𝑆(1,2,3) =’XYVW’。 JYY 定义一个“扭动的回文串”为如下情况中的一个:
- A 中的一个回文串;
- B 中的一个回文串;
- 或者某一个回文的扭动字符串𝑆(𝑖, 𝑗, 𝑘)。 现在JYY 希望找出最长的扭动回文串。 【输入格式】 从文件palindrome.in 中读入数据。 第一行包含一个正整数N。 第二行包含一个长度为N 的由大写字母组成的字符串A。 第三行包含一个长度为N 的由大写字母组成的字符串B。 【输出格式】 输出到文件palindrome.out 中。 输出的第一行一个整数,表示最长的扭动回文串。 【输入样例】 5 ABCDE BAECB 【输出样例】 5
第三轮第二试 扭动的回文串 【样例说明】 最佳方案中的扭动回文串如下所示(不在回文串中的字符用.表示): .BC.. ..ECB 【数据规模】 对于10%的数据满足 𝑁≤30。 对于30%的数据满足 𝑁≤200。 对于50%的数据满足 𝑁≤2000。 对于100%的数据满足1 ≤𝑁≤104。