显然有一个 \(|S|\log |S|\) 的 dp 做法，但是瓶颈在给字符串排序。也就是真正的瓶颈在于求 lcp。AFewSuns 给出了一种不需要科技的做法，orz。
第一个排序的部分，令 \(t_{i,j}\) 代表第 \(i\) 个字符串去掉第 \(j\) 个字符后的字符串，要给所有 \(t_{i,j}\) 排序。注意到相同颜色段是可以缩起来的，从后考虑每个连续段和下一个连续段，设为 \(c_1,c_2\)，如果 \(c_1<c_2\)，那么删去一个 \(c_1\) 肯定是不优的，同理删去 \(c_1\) 后比任意一个后面的都不优，所以删 \(c_1\) 一定是在最后面，对称的 \(c_1>c_2\) 就在最前面。
现在比较完了同一字符串，接下来比较的是两个相邻的字符串。分类讨论删去的是 \(j,k\)，如果 \(j\le k\)，分成了三个部分。\([1,j-1],[k+1,n]\) 这两个部分都可以预处理 lcp，中间部分也可以预处理错位 lcp。\(j\ge k\) 也是类似的，但是分类讨论比较麻烦。
好像讨论完这些也没什么细节了。