CF356E Xenia and String Problem

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

N/A

N/A

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.