CF356E Xenia and String Problem

程序员 Xenia 参加了信息学奥林匹克比赛，获得了一个字符串相关的问题。不幸的是，Xenia 并不擅长字符串算法。请你帮助她解决这个问题。 字符串 $s$ 是若干字符 $s_{1}s_{2}\ldots s_{|s|}$ 构成的序列，其中 $|s|$ 表示字符串的长度。 字符串 $s$ 的子串 $s[i\ldots j]$ 为 $s_{i}s_{i+1}\ldots s_{j}$。 若字符串 $s$ 满足以下条件，则称为 Gray 字符串： - 字符串长度 $|s|$ 是奇数； - 某个字符 $\alpha$ 在字符串中恰好出现一次； - 若 $|s|=1$，或$|s| > 1$ 时，子串 $s[1\ldots \frac{|s|-1}{2}]$ 与 $s[\frac{|s|+3}{2}\ldots |s|]$ 相同，且均为 Gray 字符串。 例如，字符串 "abacaba"、"xzx"、"g" 是 Gray 字符串，而字符串 "aaa"、"xz"、"abaxcbc" 不是。 定义字符串 $p$ 的美丽值为 $p$ 的所有子串中是 Gray 字符串的那些子串长度的平方之和。也就是说，考虑所有满足 $1 \leq i \leq j \leq |p|$ 的 $i,j$ 对，如果子串 $p[i\ldots j]$ 是 Gray 字符串，则向美丽值中加上 $(j-i+1)^2$。 Xenia 拥有一个仅包含小写英文字母的字符串 $t$。她最多可以将其中的一个字母替换为任意其他英文字母。你的任务是经过最多一次替换后，使所得字符串的美丽值最大。

第一行一个非空字符串 $t$，满足 $1 \leq |t| \leq 10^5$。字符串 $t$ 仅包含小写英文字母。

输出 Xenia 能够获得的最大美丽值。 请不要在 C++ 中使用 %lld 读写 64 位整数。推荐使用 cin/cout 或 %I64d。

在第一个测试样例中，原字符串可以变为 $p = \mathrm{zbz}$。该字符串的 Gray 子串有 $p[1\ldots1]$, $p[2\ldots2]$, $p[3\ldots3]$ 和 $p[1\ldots3]$。美丽值总和为 $1^2+1^2+1^2+3^2=12$。无法获得更高的美丽值。 在第二个测试样例中，不进行任何操作即可获得最大美丽值。 由 ChatGPT 5 翻译