最小表示法

题目链接：最小表示法

最小表示法就是针对一个字符串，得到其同构循环串的最小字典序的一个

同构循环串：这里可以用一个队列方便理解：比如对于“123456789”，我们不断弹出队头将其放到队尾，得到的字符串即为其同构循环串

为了方便得到其算法，我们可以拿到一个数据进行模拟：

对于数据 2 3 6 5 1 7 8 9 3 0 我们要解决两个问题

①如何存储其所有同构循环串？我们不需要用到队列，只需要将其复制一遍放到其末尾即可。于是就成为了2 3 6 5 1 7 8 9 3 0 2 3 6 5 1 7 8 9 3 0

②如何得到其最优字符串？假如字符串长度为n，对于s[i]，我们很容易知道s[i]-s[i+n]这一段字符串是其一个同构循环串。比较字典序我们需要一个一个进行比较。因此我们可以指定两个指针i=0，j=1，让k从0循环到n，比较s[i+k]和s[j+k]，这样子就可以得到其每一位的大小。

1.若s[i+k]>s[j+k]，则说明0-i+k的所有字符串均不是最优解，所以i = i+k+1

2.若s[i+k]<s[j+k]，则说明0-j+k的所有字符串均不是最优解，所以j = j+k+1

3.若两者相等，则继续循环

4.最后得到的最小的k即为最优解开始的下标

算法是显而易见的，时间复杂度从枚举的O(n^2)变成了O(n)，效率是显然的

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int N = 6e5+10;
int q[N],n; 

int main()
{
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >> q[i];
        //构造同构循环串
        q[i+n] = q[i];
    }
    int i=1,j=2,k;//i,j为双指针
    while(i<=n && j<=n)
    {
        //找到第一个不同的位置
        for(k=0;k<n;k++)
            if(q[i+k]!=q[j+k])
                break;
        //如果整个字符串都是相同的，说明原字符串就是答案
        if(k == n) break;
        //0-i+k都不是最优解
        if(q[i+k]>q[j+k])
        {
            i = i+k+1;
            if(i == j) i++;
        }
        //同理
        if(q[i+k]<q[j+k])
        {
            j = j+k+1;
            if(i == j) j++;
        }
    }
    k = min(i,j);
    for(int i=0;i<n;i++) cout << q[i+k] << " ";
    return 0;
}