专栏文章

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

KKobeBeanBryantCox
P1368题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipqj5ii
此快照首次捕获于
2025/12/03 16:18
3 个月前
此快照最后确认于
2025/12/03 16:18
3 个月前
查看原文

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

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

算法介绍

1. 循环同构

若有一个字符串 S=dcabS=\texttt{dcab}，则以下字符串组叫做 SS 的循环同构：
  • dcab\texttt{dcab}
  • cabd\texttt{cabd}
  • abdc\texttt{abdc}
  • bdca\texttt{bdca}
简单来说就是每次把 SS 的第一个字符拿出来放到最后，重复做 ∣S∣|S| 次得到的字符串组。

2. 最小表示法

最小表示法就是用来求一个字符串的循环同构中，字典序最小的那个，在原串的起始位置。
例如在上面 S=dcabS=\texttt{dcab} 的例子中，字典序最小的是 abdc\texttt{abdc}，在原串起始位置为 22（从 00 开始），最小表示法就返回这个 22。
怎么找呢？
先破环成链（复制一遍拼到后面），比如有个字符串 S=acbacbcS=\texttt{acbacbc}，破环成链后是 S′=acbacbcacbacbcS'=\texttt{acbacbcacbacbc}。
考虑维护两个指针 i,ji,j 表示当前比较的两个循环同构的起点，和一个变量 kk 表示长度减一（减一是因为方便）。
对于每一组 (i,j)(i,j)，kk 从 00 开始枚举匹配。
比如上面 S′S'，当 i=0,j=3,k=3i=0,j=3,k=3 时匹配情况如下：
&i\\ &\underline{\texttt{acb\color{blue}a}}\texttt{cbcacbacbc}\\ &\texttt{acb}\underline{\texttt{acb\color{blue}c}}\texttt{acbacbc}\\ &\texttt{ }\texttt{ }\texttt{ }j\\ \end{aligned}$$ 我们发现 $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)$ 的，这部分在代码也能很好地体现。 ------------- ## 代码实现 我的代码并没有破环成链，不过基本思想是一样的。 ```cpp #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; } ``` ----------------- 若不清或有误，欢迎评论或私信。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...