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

KobeBeanBryantCox · 2025-04-02 17:03:04 · 题解

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

题目传送门。

既然是最小表示法的题目，我就来讲讲最小表示法。

算法介绍

1. 循环同构

若有一个字符串 S=\texttt{dcab}，则以下字符串组叫做 S 的循环同构：

• \texttt{dcab}
• \texttt{cabd}
• \texttt{abdc}
• \texttt{bdca}

简单来说就是每次把 S 的第一个字符拿出来放到最后，重复做 |S| 次得到的字符串组。

2. 最小表示法

最小表示法就是用来求一个字符串的循环同构中，字典序最小的那个，在原串的起始位置。

例如在上面 S=\texttt{dcab} 的例子中，字典序最小的是 \texttt{abdc}，在原串起始位置为 2（从 0 开始），最小表示法就返回这个 2。

怎么找呢？

先破环成链（复制一遍拼到后面），比如有个字符串 S=\texttt{acbacbc}，破环成链后是 S'=\texttt{acbacbcacbacbc}。

考虑维护两个指针 i,j 表示当前比较的两个循环同构的起点，和一个变量 k 表示长度减一（减一是因为方便）。

对于每一组 (i,j)，k 从 0 开始枚举匹配。

比如上面 S'，当 i=0,j=3,k=3 时匹配情况如下：

我们发现 S_{i+k}<S_{j+k}，这意味着：

1. 从 i 开始的循环同构要优于从 j 开始的；
2. 从 i+1 开始的循环同构优于从 j+1 开始的；
3. \cdots
4. 从 i+k 开始的循环同构优于从 j+k 开始的。

所以所有 j\sim j+k 开始的循环同构，都会被淘汰。

这个时候把 j 赋值为 j+k+1，把 k 清零，继续比较。

没看懂的可以结合代码理解。

正确性证明

正确性显然。现在来证明复杂度是 O(n) 的。

考虑指针 i,j 位移的大小。

每次比较向后扫描 k 的长度，则 i 或者 j 会向右移动 k，此时 i 和 j 一共最多会移动 2n 个位置。

所以复杂度是 O(n) 的，这部分在代码也能很好地体现。

代码实现

我的代码并没有破环成链，不过基本思想是一样的。

#include<bits/stdc++.h>
#define Code using
#define by namespace
#define wjb std
Code by wjb;
int in()
{
    int k=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')k=k*10+c-'0',c=getchar();
    return k*f;
}
void out(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x<10)putchar(x+'0');
    else out(x/10),putchar(x%10+'0');
}
const int N=3e5+10;
int a[N];
int minshow(int n)
{
    int i=0,j=1,k=0; // 赋初值
    while(i<n&&j<n&&k<n) // 这是循环的条件
        if(a[(i+k)%n]==a[(j+k)%n])k++; // 如果相等，就暴力往后扫描 k
        else
        {
            if(a[(i+k)%n]>a[(j+k)%n])i+=k+1; // i 的位置劣于 j，将 i 赋值为 i+k+1
            else j+=k+1; // 否则将 j 赋值为 j+k+1
            if(i==j)i++; // 若相同是没有意义的，随便偏移一位即可
            k=0; // 清零 k 重新扫描
        }
    return min(i,j); // 此时要么 i==n，要么 j==n，返回 min(i,j) 就能得到正确的位置。注意这里如果是因为 k==n 退出的，说明字符串都是同一个字符，随便返回一个都行，所以也可以用 min(i,j)
}
int main()
{
    int n=in();
    for(int i=0;i<n;i++)a[i]=in();
    int ans=minshow(n);
    for(int i=0;i<n;i++)out(a[(i+ans)%n]),putchar(' ');
    return 0;
}

若不清或有误，欢迎评论或私信。