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

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

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

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

证明

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

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

2l <= r 情况示例
2l <= r 情况示例

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

如何运用

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

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