D. 重复序列

时间限制: 1000ms 空间限制: 65536kb

题目描述

有这样一个只包含小写字母的字符串 s。

重复序列是一个偶数长度的字符串，其前半部分等于后半部分。 我们可以进行以下两种操作：

操作1，我们可以删除字符串s的开头几个（可能是零个或全部）字符和结尾的几个（可能是零个或全部）字符。

操作2，我们可以选择其中一种字符，可以任意变换成其他字符。（例如，比如选择的是字符a这种字符，那么对于每一个a字符都可以更改为a~z任意一种字符。）

我们的目标是经过以上操作后，使得重复序列的最长子串尽可能的大。

输入格式

输入一个字符串s ,s.length() <= 1000

输出格式

输出一个整数，重复序列的最长子串的最大长度，如果字符串中不可能有重复序列的子串，则输出0。

输入输出样例

Input 1:

zaabaabz

Output 1:

6

Input 2:

zaabaaaz

Output 2:

8

zaabaaaz

样例解释

对于样例1最长的重复序列为把字符串前年去掉一个字符后面去掉一个字符得到aabaab长度为6的重复序列。

对于样例2来说我们可以选择字符z可以任意变换成其他字符，这样的话我们选择第一个z变成a，最后一个字符变成b，得到aaabaaab这个重复序列，长度为8。