#P2165. 纹样拼接
纹样拼接
本题需要文件读写
文件 IO 为:输入文件
lacquer.in,输出文件lacquer.out。请使用上述文件名读入和输出。
问题描述
有一块长度为 的漆板,上面刻有字符串 。其中一段连续的位置有金色标记,字符串 用 1 表示有金色标记的位置,用 0 表示没有标记的位置;也可能没有任何金色标记。
需要从 中选出若干段不重叠的连续子串,按它们在原串中出现的先后顺序拼接,并满足:
- 拼接得到的字符串是回文串,即从左往右读和从右往左读完全相同。
- 原串中所有有金色标记的位置,必须被同一段选中的子串完整覆盖。
请计算满足条件的最长回文串的长度。如果不存在满足条件的方案,输出 0。
输入格式
从文件 lacquer.in 中读入数据。
第一行输入一个整数 ,表示漆板长度。
第二行输入一个长度为 的字符串 ,只包含小写英文字母。
第三行输入一个长度为 的字符串 ,只包含字符 0 和 1。保证所有 1 出现在一个连续区间内,也可能没有 1。
输出格式
输出到文件 lacquer.out 中。
输出一行一个整数,表示满足条件的最长回文串长度。
样例输入 1
4
abba
0000
样例输出 1
4
样例输入 2
6
abccba
011100
样例输出 2
6
样例输入 3
11
abcdxyedcba
01100000000
样例输出 3
9
样例输入 4
23
abcdefghijxyzjihgfedcba
00111000000000000000000
样例输出 4
21
样例输入 5
15
abcdeffedcbaxyz
000011110000000
样例输出 5
12
评测数据规模
对于所有数据,保证 ,,其余条件如输入格式所述。
每个测试点 分,各测试点附加限制如下。
| 测试点 | |
|---|---|