最小表示法

概念

循环同构串：我们有字符串 bcad ，那么它的循环同构串可以是 bcad,cadb,adbc,dbca。

最小表示法可以用来找出字符串 S （或者数组）的循环同构串中字典序最小的一个。

实现方法

复杂度 $O(N)$。

假设有一个字符串 $S$ ,设 $S$ 的长度为 $n=|S|$，思考如下：

1. 两个指针 $i$ 、$j$ ，初始化时 $i$ 指向 $s_{0}$，j 指向 $s_{1}$ 。我们规定 $i$ 和 $j$ 在任意时刻都不能相等。

2. 匹配长度 $k = 0$ 开始，检验 $s_{i + k}$ 和 $s_{j + k}$ 是否相等，相等则 $k \gets k+1$，一直循环下去，直到找到第一个不相同的字符。（若 $k = n$ 则全字符串相等）

3. 在遇到第一个不相同字符的过程中，我们发现 $s_{i + k}$ 和 $s_{j + k}$ 的关系有两种：

   • $s_{i + k} > s_{j + k}$ ，显然 此时以 $i$ 为开头必然不使字典序最小，所以 $i \gets i+k+1$。
   • $s_{i + k} < s_{j + k}$ ，同理，$j \gets j+k+1$。

4. 当 $i,j,k$ 中有一个等于 $n$，循环结束，返回 $\min(i，j)$。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int n, S[300009];
int Min_show() {
    int i = 0, j = 1, k = 0;
    while (i < n && j < n && k < n) {
        if (S[(i + k) % n] == S[(j + k) % n])
            k ++;
        else {
            if (S[(i + k) % n] > S[(j + k) % n])
                i += k + 1;
            else
                j += k + 1;
            if (i == j)
                i++;
            k = 0;
        }
    }
    return min(i, j); //返回最小表示
}

习题

P1368 最小表示法