一个关于将字符串划分为符合条件的回文子串的结论

如果遇到了关于将字符串划分为符合条件的回文（比如长度为偶数的回文）子串，有可能会用到这个定理：

如果字符串可以被划分的话，它的最大划分是唯一的，并且可以通过从左往右贪心地选择最短的回文子串来得到最大划分。这里的“最大”指划分为回文子串的个数。

第一次接触到这个结论是在 Codeforces 1827C 的题解中，后面会附上题解里证明的翻译。最近又在23 年牛客多校第二场的 G 题遇到了这个结论。后面会简单地讨论这两个题。

证明 #

假设字符串 $t$ 当前有一个划分的第一部分是 $t[0, r)$，$t[0, l)$ 是最短的前缀回文子串。我们要证明如果 $l < r$，我们可以构造出子串数量更多的划分。考虑两种情况：

$2l \le r$：很明显 $t[0, l), t[l, r - l), t[r - l, r)$ 都是回文子串，我们可以将 $t[0, r)$ 替换成它们。

$2l > r$：$t[r - l, l)$ 是回文子串（因为关于重心对称），其在 $t[0, l)$ 中的对称部分为 $t[0, 2l - r)$，所以 $t[0, 2l - r)$ 也是回文子串，与我们的假设矛盾，所以不会出现这种情况。

如何运用 #

对于 Codeforces 的那个题，我们对于每个位置找到最短在此结束的回文子串，然后进行状态转移。

对于牛客那个题（以及一般的判断能否划分的问题），我们维护最长的可以被划分的前缀，如果以当前位置为中心的回文子串可以扩展该前缀，我们就扩展该前缀。这本质就是贪心地选择最短的回文子串。