题解：P1368 【模板】最小表示法

NBAchampions · 2025-01-13 11:51:12 · 题解

前言

本做法不为最优解，但十分好想且无脑。

废话

由于本题是 最小表示法 的模板题，所以我们考虑不使用 最小表示法。

正文

考虑把序列长度扩大至 2 倍，则每一种表示法都能对应到新序列上一个长度为 n 的区间。

考虑直接比较，复杂度最坏为 O(n^2)，不可通过。

考虑哈希，我们可以在 O(1) 复杂度内求出一段区间内的哈希值。对于比较两个长度为 n 的字符串时，我们可以二分到第一个哈希值不同的位置，也就是两个字符串第一个字符不同的位置。比较这个位置的大小，即可比较出这两个字符串的大小。于是我们可以在 O(\log n) 的复杂度内完成两个字符串的比较。

由于最多有 n 种表示法，所以总复杂度为 O(n\log n)。

后记

像这种哈希 + 二分比较的做法除了可以应用到最小表示法外，常见的应用还有后缀数组等。虽然复杂度多一只 \log，但如果在考场上忘记正解时也是一种好方法。