Xenia and String Problem

题意翻译

定义一个字符串 $s$ 是好的当且仅当： 1. $|s|$ 是奇数。 2. $s_{\frac {|s|+1}2}$ 在 $s$ 中仅出现一次。 3. $|s|=1$，或者 $s[1, \frac {|s|-1}2]=s[\frac{|s|+3}2,|s|]$ 且这两个串都是好的。 定义一个字符串的权值为长度的平方。 定义一个字符串的美丽值为其所有子串中，好的字符串的权值和。 给定字符串 $S$，你可以至多修改 $S$ 的一个字符。求修改后的 $S$ 的美丽度的最大值。

题目描述

Xenia the coder went to The Olympiad of Informatics and got a string problem. Unfortunately, Xenia isn't fabulous in string algorithms. Help her solve the problem. String $ s $ is a sequence of characters $ s_{1}s_{2}...\ s_{|s|} $ , where record $ |s| $ shows the length of the string. Substring $ s[i...\ j] $ of string $ s $ is string $ s_{i}s_{i+1}...\ s_{j} $ . String $ s $ is a Gray string, if it meets the conditions: - the length of string $ |s| $ is odd; - character  occurs exactly once in the string; - either $ |s|=1 $ , or substrings  and  are the same and are Gray strings. For example, strings "abacaba", "xzx", "g" are Gray strings and strings "aaa", "xz", "abaxcbc" are not. The beauty of string $ p $ is the sum of the squares of the lengths of all substrings of string $ p $ that are Gray strings. In other words, consider all pairs of values $ i,j $ $ (1<=i<=j<=|p|) $ . If substring $ p[i...\ j] $ is a Gray string, you should add $ (j-i+1)^{2} $ to the beauty. Xenia has got string $ t $ consisting of lowercase English letters. She is allowed to replace at most one letter of the string by any other English letter. The task is to get a string of maximum beauty.

输入输出格式

输入格式

The first line contains a non-empty string $ t $ $ (1<=|t|<=10^{5}) $ . String $ t $ only consists of lowercase English letters.

输出格式

Print the sought maximum beauty value Xenia can get. Please do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

zzz

输出样例 #1

12

输入样例 #2

aba

输出样例 #2

12

输入样例 #3

abacaba

输出样例 #3

83

输入样例 #4

aaaaaa

输出样例 #4

15

说明

In the first test sample the given string can be transformed into string $ p $ = "zbz". Such string contains Gray strings as substrings $ p[1...\ 1] $ , $ p[2...\ 2] $ , $ p[3...\ 3] $ и $ p[1...\ 3] $ . In total, the beauty of string $ p $ gets equal to $ 1^{2}+1^{2}+1^{2}+3^{2}=12 $ . You can't obtain a more beautiful string. In the second test case it is not necessary to perform any operation. The initial string has the maximum possible beauty.