研究字符串的最小表示方法

最小表示法

字符串的最小表示法具有多种定义形式，例如集合的最小表示法、字符串的最小表示法等。

本文将重点介绍字符串的最小表示法。

以一个示例字符串ababc为例。

可通过循环移动的方式生成 n 个不同的字符串。所谓循环移动，即将首字符移动至字符串末尾，具体如下：

1. 循环 1 位后得到babca；
2. 循环 2 位后得到abcab；
3. 循环 3 位后得到bcaba；
4. 循环 4 位后得到cabab；

在这些生成的字符串中，字典序最小的那个即为原字符串的最小表示法。

• 若采用暴力方法解决该问题，其时间复杂度为 O(n^2).

首先需要构造出所有 n 个可能的循环字符串，此过程的时间复杂度即为 O(n^2)。随后还需逐一比较这些字符串以确定字典序最小者。

然而，存在一种算法能够将时间复杂度优化至 O(n)。

* 可以观察到，每次循环操作均是将首字符移至末尾。因此可考虑采用“破环成链”的策略，即将所有可能的循环字符串映射到一条链上。

具体而言，可以将原始字符串复制一份并连接至其末尾，使得总长度变为两倍于原长度即为 2n.