题解：AT_abc237_h [ABC237Ex] Hakata

· · 题解

Solution

一个经典结论是：一个字符串只有 O(n) 个本质不同的回文子串。可以用数学归纳法证明。

这样可以直接建出回文子串之间的包含关系，包含关系本质上是一种偏序关系。

因此问题等价于 DAG 上的最长反链。

根据 Dilworth 定理，最长反链等于最小点覆盖。跑二分图匹配即可。